이진 탐색 2 (Binary Search)

 이진 탐색은 정렬되어 있는 요소들에게만 사용할 수 있다. 일반적인 순차 탐색으로는 O(N)의 시간이 소요되지만, 이진 탐색을 사용하면 O(log N) 시간이 소요된다. 

 

 C++로 구현한 기본적인 구현은 다음과 같다.

int binarySearch(int key)
{
	int low = 0;
	int high = MAX - 1;

	while (low <= high)
	{
		int mid = (low + high) / 2;

		if (key > arr[mid])
		{
			low = mid + 1;
		}
		else if (key < arr[mid])
		{
			high = mid - 1;
		}
		else
		{
			return mid;
		}
	}

	return -1;
}

 이 코드는 key가 정해진 배열에 존재하는지 여부를 판단할 수 있고, 만약 있다면 그 인덱스를 리턴하고, 없다면 -1을 리턴한다. 배열에서 key의 존재 유무를 판단하는 것이 주요한 역할이다.

 

 다양한 이진 탐색 문제에서 중요한 것은 lower_bound 와 upper_bound 이다. 이는 중복된 값이 존재하는 배열에서의 이진 탐색에서 유용하다.

lower_bound는 key로 주어진 값과 같거나 큰 첫번째 요소를 리턴하게 된다. C++로 구현한 코드는 다음과 같다.

int lowerBound(int key)
{
	int low = 0;
	int high = MAX - 1;

	while (low < high)
	{
		int mid = (low + high) / 2;

		if (key <= arr[mid])
		{
			high = mid;
		}
		else
		{
			low = mid + 1;
		}
	}

	return low;
}

 기본적인 이진 탐색과의 차이는 첫번째로 low <= high에서 low < high로 바뀌었다는 점이고, 두번째로는 정확한 값을 찾은 즉시 리턴하는 것이 아니라 조건을 만족하는 첫번째 요소를 찾아야 하기 때문에 low < high를 만족하지 않을 때까지 반복하는 점이다. 예를 들어 arr[] = { 1, 2, 2, 2, 3, 3, 7, 7 } 에서 lowerBound(3) 은 4를 리턴하고, lowerBound(5) 는 6을 리턴한다.

 

 upper_bound는 key 보다 큰 값이 처음으로 나오는 인덱스를 리턴한다. 구현 코드는 다음과 같다.

int upperBound(int key)
{
	int low = 0;
	int high = MAX - 1;

	while (low < high)
	{
		int mid = (low + high) / 2;

		if (key < arr[mid])
		{
			high = mid;
		}
		else
		{
			low = mid + 1;
		}
	}

	return low;
}

 lowerBound 와 다른 점은 if 문에서 key <= arr[mid] 에서 key < arr[mid] 로 바뀌었다는 것이다. 

 

 lowerBound 와 upperBound 구현 코드의 문제점은 만약 arr[] = { 1, 2, 2, 2, 3, 3, 7, 7 } 에서 key 가 8일때이다. 8보다 크거나 같은 값이든 8보다 큰 값이든 arr 안에는 존재하지 않으나, 이를 실행해보면 7이 리턴된다. 이를 방지하기 위해서는 배열의 가장 마지막 요소의 값을 확인해줘야 한다. 

 

 C++에서는 이와 같은 함수들을 이미 헤더 <algorithm> 에서 제공한다. binary_search() 함수에서는 key가 존재하는지 아닌지 유무만을 판단해주고, lower_bound() 와 upper_bound() 에서는 위와 동일한 결과를 도출한다. 큰 차이점은 key 가 배열 안의 모든 요소들보다 클 경우에는 마지막 인덱스 + 1, 즉 배열의 크기를 리턴하게 된다. vector 의 경우에는 arr.end() 이터레이터를 리턴한다. 

 

 

 

참고

- https://en.wikipedia.org/wiki/Binary_search_algorithm