이진 탐색을 자명하지 않은 형태로 다양하게 활용할 수 있다.
이진탐색은 탐색 공간을 확인할 때마다 탐색 공간의 크기가 절반으로 줄어들기 때문에 시간 복자도가 $O(\log n)$이다. C++STL의 lower_bound()등에서 이진탐색을 지원한다.
문제를 요약하면 다음과 같다.
어떤 가중치가 있는 트리가 정점은 $N\le 8$만개이고, 정점의 가중치가 루트에서 리프로 갈수록 점점 커진다는 특성을 만족한다. 시작 정점 v가 주어졌을 때 이 정점의 조상 중에서 그 가중치가 적어도 P이상 이면서도 루트에서 가장 가까운 것을 구하라.
같은 트리에 대하여 질의가 Q번 이루어진다.
단순한 방법으로는 각 질의 마다 선형 시간 탐색하는 것이다. 이 경우 시간 복잡도가 $O(QN)$이므로 TLE가 나오게 된다.
이진 탐색을 이용해보자. 트리에 대해서 $O(N)$의 시간복잡도를 소모하는 전위탐색을 하자. 이때 루트에서 특정 리프까지를 수열로 저정해 놓는다. 그리고 전위 순회 도중에 질의에 포함된 정점을 만나게 되면, 루트부터 현재 정점까지의 부분적인 가중치 수열에 대해 $O(\log N)$이진 탐색을 수행한다. 최종적으로는 $O(Q)$루프를 수행하면서 저장해둔 답을 단순히 출력하기만 하면 된다. 이 방식의 전체 시간 복잡도는 $O(Q\log N)$이고, 이 정도면 주어진 범위의 입력을 처리할 수 있다.