4-1. 이진 탐색(Binary Search)

1. 이진 탐색(Binary Search)

배열에 데이터가 정렬되어 있는 상황을 보자.

v = { 1, 8, 15, 23, 32, 44, 56, 63, 81, 91 };

여기에서 82라는 숫자가 배열에 있는지 찾을 수 있을까?

이진 탐색을 이용하면 반복자를 이용하여 O( N )의 시간 복잡도로 찾는 방법보다 더 빠른 탐색이 가능하다.

대략 중간에 위치한 인덱스를 이용하여 그 인덱스의 데이터와 82를 비교하여 더 작으면

더 작은 절반을 날리는 식으로 탐색을 수행한다.

(시간 복잡도 = O ( log N ) )

 

2. 이진 탐색 구현 - 이미 정렬된 배열 탐색하기

void BinarySearch(int N)
{
	int left = 0;
	int right = (int)numbers.size() - 1;
	bool found = false;

	while (left < right)
	{
		int mid = (left + right) / 2;

		if (numbers[mid] > N)
		{
			right = mid;
		}

		if (numbers[mid] < N)
		{
			left = mid + 1;
		}

		if (numbers[mid] == N)
		{
			found = true;
			break;
		}
	}

	if (found)
		cout << "찾았다";
	else
		cout << "못찾았다";
}

3개의 인덱스 left (왼쪽 절반의 맨 앞), right (오른쪽 절반의 맨 뒤), mid ( left와 right의 중간 값)를 이용한다.

제시된 숫자가 numbers 배열의 값보다 작으면 왼쪽 인덱스를 중앙으로 당겨와서 오른쪽 절반을 탐색한다.

제시된 숫자가 numbers 배열의 값보다 크면 오른쪽 인덱스를 중앙으로 당겨와서 왼쪽 절반을 탐색한다.

 

3. 이진 탐색의 한계

(1) 정렬되지 않은 배열에서는 적용하기 어려움

(2) 정렬된 연결 리스트에서는 임의접근이 불가능하므로 인덱스로 탐색이 불가능함

(3) 벡터의 특성 상 데이터 중간 삽입 & 삭제가 느림