이진 탐색 알고리즘은 로그 시간 복잡도를 보여주는 대표적인 탐색 알고리즘이다. 정렬된 컨테이너에서 어떤 요소를 찾아야 한다면, 우선적으로 고려해봐야 하는 알고리즘 중 하나이다. 만약, STL을 사용하고 있다면 이진 탐색을 적용하는 것은 매우 쉽다. STL 알고리즘은 binary_search, lower_bound, upper_bound, equal_range와 같은 로그 시간 복잡도를 가지는 탐색 함수들을 이미 가지고 있다.
그러나, 때로는 이들 함수를 직접 적용하는 것이 가끔 곤란할 때가 있다. 즉, binary_search는 이진 탐색 함수이기는 하지만 컨테이너에서 주어진 값을 가진 원소가 있는지 없는지만 알려줄 뿐, 컨테이너 내에서의 원소 위치를 알려주지 않는다. lower_bound의 경우, 주어진 범위 내에서 주어진 값과 일치하는 원소의 위치를 찾아주는데, 원소의 위치는 주어진 값과 일치하는 원소의 바로 앞이다. upper_bound는 주어진 값과 일치하는 원소의 가장 마지막 바로 다음이다. lower_bound와 upper_bound는 결과값이 약간 불편한데, 이것은 결과값인 반복자의 위치에 어떤 원소를 삽입하는 상황을 고려했기 때문이다. equal_range는 lower_bound, upper_bound를 모두 적용하여 주어진 값이 있는 원소의 범위를 std::pair 형태로 돌려주기 때문에, 이들이 모두 로그 시간 복잡도를 보여준다고 하더라도 흔히 생각하는 직관적인 이진 탐색 방법은 아니다.
더구나, equal_range는 lower_bound, upper_bound 모두를 사용하기 때문에 그다지 반갑지 않다. 물론, lower_bound나 upper_bound를 사용하는 것도 나쁘지는 않지만, 경우에 따라 이진 탐색 알고리즘을 직접 작성하는 것이 더 간단할 때가 있다. 알고리즘은 다음과 같다.
std::size_t mid = 0, begin = 0, end = N; // N is number of array elements
while(begin < end)
{
mid = begin + ((end - begin) / 2);
if(Array[mid] < value)
begin = mid + 1;
else end = mid;
}
if((begin < N) && (Array[begin] == value))
return Array[begin];
return 0;
이것은 널리 알려진 이진 탐색 알고리즘이며, 코드를 더 줄이는 것은 쉽지 않을 것이다. 그러나, 이 코드가 최고의 효율을 보여준다는 것은 아니다. 특히 STL 컨테이너들을 사용하는 경우, STL 라이브러리 제작자들은 보다 효과적으로 STL 알고리즘들을 구현할 수 있는 수단이 많기 때문에, 같은 일을 한다면 가급적 STL 알고리즘을 사용하는게 훨씬 낫다.
다만, [] 연산자를 통해 직접 컨테이너에 접근할 수 있는 경우, STL 알고리즘을 사용하기 위해 필수적으로 작성해야 하는 비교 함수나 비교 함수자를 사용하는 것보다 이런 구성을 취하는게 훨씬 더 간단할 수 있다는 뜻이다.
Library/C/C++
