이진탐색의 확장 - 트리에서의 효율적인 탐색
서론 이진탐색은 정렬된 $N$개의 원소가 있을 때, 원하는 수의 위치를 $O(\log N)$ 시간에 찾는 테크닉이다. 이 글에서는 이진탐색을 트리로 확장할 것이다. 그리고 트리에서도 원하는 수의 위치를 $O(\log N)$시간에 찾을 수 있다는 증명과, 비교연산을 최소로 하는 방법을 설명할 것이다. 이진탐색 탐색이란 숨겨진 $a$ 이상 $b$이하의 정수 $x$에 대해, 이 $x$를 찾는 과정이다. 이진탐색에서는 다음과 같은 질문을 할 수 있다: “어떤 수 $y$ 에 대해, $y$와 $x$의 대소관계는 무엇인가?” $y$가 $x$보다 크다는 답이 돌아오면, 우리는 $x$가 $y+1$...