이분 탐색은 탐색 시간이 자료 크기의 로그스케일에 바운드되는 자료 검색 알고리즘이다.
어떤 자료 a가 이분 탐색을 할 수 있으려면
1. 어떤 조건식 bool f(element)를 상수함수로 가져야 한다.
2. 참인 요소와 거짓인 요소가 완전히 분리되어있어야 한다. 좀 더 수식적으로 엄밀하게 표현하면 i<j<k인 인덱스에 대해 f(a[i])!=f(a[j])!=f(a[k])인 i,j,k쌍이 없어야 한다.
두 조건을 만족해야 한다. 이때 찾는 값은 f(a[i-1])!=f(a[i])인 i, f에 대한 평가가 달라지는 가장 작은 인덱스 또는 f에 대한 평가가 달라지는 경계의 바로 오른쪽 인덱스이다.
2번 조건은 f(a[i-1])!=f(a[i])가 존재하면 유일하다는 것을 의미한다. 예를 들어 f(a[i-1])!=f(a[i])이고 f(a[j-1])!=f(a[j])라면 WLOG i<j에서 1. f(a[i])==f(a[j-1]), 2. f(a[i])!=f(a[j-1])인데 1의 경우 i-1<i<j, 2의 경우 i-1<i<j-1이 2의 조건을 만족하지 못한다. 따라서 답이 존재하면 유일하다. 좀 더 자연스럽게 표현하면 평가가 참인 요소는 모두 전체가 연속해야하고, 평가가 거짓인 요소는 모두 전체가 연속해야 한다. 좀 더 쉽게 표현하면 f에 대한 평가를 기준으로 정렬되어있어야 한다.
만약 모든 요소의 평가가 같다면 어떨까? WLOG 왼쪽의 평가를 거짓, 오른쪽의 평가를 참이라고 강제하고 생각해보면 f(a[i-1])!=f(a[i])라는게 사실은 f(a[i-1])이 거짓, f(a[i])가 참인 i를 반환하는 것으로 생각할 수 있으므로 모든 n개의 평가가 참이라면 i=0, 거짓이라면 i=n을 반환하는 것으로 볼 수 있다 (0-index). 이때 i=n은 대응하는 자료의 값이 없어 컴퓨터에서는 할당되지 않은 메모리를 가리킬 수 있음에 유의해야 한다.
이분 탐색의 원리는
1. 왼쪽 끝과 오른쪽 끝의 평가가 다른 어떤 구간을 알고 있다. WLOG, 왼쪽의 평가를 거짓, 오른쪽의 평가를 참이라고 할 수 있다. 반대이면 f의 평가를 뒤집는 함수를 생각하는 것으로 충분하다.
2. 여기서 구간 가운데 어떤 인덱스를 잡는다. 이 인덱스가 가리키는 요소의 평가는 참 또는 거짓이다. 이때 조건 2에 의해 평가가 참인 경우 현재 인덱스와 왼쪽 끝의 평가가 다르고, 평가가 거짓인 경우 현재 인덱스와 오른쪽 끝의 평가가 다르다.
3. 이는 1에서 찾은 양 끝의 평가가 다른 어떤 구간보다 작은 구간이다. 따라서 1을 크기가 더 작은 부분구간에 대해 반복할 수 있다. 더이상 2에서의 가운데 인덱스를 잡을 수 없을 때까지 반복한다. 이때의 오른쪽 끝이 구하고자 하는 답이 된다.
의 반복으로 저런 인덱스를 찾을 수 있다는 것이다. 여기서 가운데 인덱스를 잡는 방법에 따라 시간복잡도가 결정되는데, 가운데 인덱스를 정확히 구간의 가운데로 잡으면 자료의 순서에 관계없이 크기의 로그스케일에 바운드된다.
예를 들어 자료 a=[1,1,2,2,3,4,6,6,7]에서 f(x) = "x>=5"의 평가를 기준으로 이분탐색을 하려고 한다. 자연어로 표현하면 5 이상인 가장 작은 인덱스를 찾으려고 한다. 0-index를 기준으로 구간 [0,8]은 왼쪽 끝과 오른쪽 끝의 평가가 다른 구간이다. 구간의 가운데인 인덱스 4를 잡았다. f(a[4])는 "3>=5"로 거짓이므로 구간 [4,8] 또한 평가가 다른 조건을 만족하는 더 작은 구간이다. 다시 구간의 가운데인 인덱스 6을 잡으면 f(a[6])은 "6>=5"로 참이므로 [4,6] 또한 평가가 다른 조건을 만족하는 더 작은 구간이다. 다시 구간의 가운데인 인덱스 5를 잡으면 f(a[5])는 "4>=5"로 거짓이므로 [5,6] 또한 평가가 다른 조건을 만족하는 더 작은 구간이다. 이때 더이상 가운데 구간을 잡을 수 없고, 5+1==6이므로 f(a[i-1])!=f(a[i])를 만족하는 인덱스 i=6을 찾았다.
C++ STL의 std::upper_bound/lower_bound를 비롯한 많은 언어가 이런 이분 탐색의 특정 케이스를 지원한다. 특히 std::upper_bound는 어떤 값 t를 받아 f(x) = "t<x"를 기준으로, std::lower_bound는 f(x) = "t<=x"를 기준으로 이분 탐색을 진행한다. 자연어로 설명하면 upper_bound는 초과를 기준으로, lower_bound는 이상을 기준으로 이분탐색을 진행한다. 또한 std::upper_bound/lower_bound는 네번째 인자를 람다로 받을 수 있는 오버로딩이 되어 있어 연산자 <, <=를 람다 형식으로 넘길 수도 다.