그림 8-1은 이진 탐색에서 첫 번째 반복문을 나타냅니다. middle=(start+end)//2이므로 2입니다. 이제 li[middle] 값과 target을 비교합니다. target이 더 작군요. 요소들이 정렬된 상태라는 전제 조건이 있기 때문에 middle 이후의 요소들이 4일 확률은 없지요. 그럼 이 부분은 비교할 필요가 없습니다. 그럼 end를 middle-1로 만듭니다. 이렇게 반복문이 실행되면서 start와 end가 교차하기 전에 target 값이 있다면 찾을 것입니다. 그럼 리스트 크기가 n일 때 빅오는 어떻게 될까요? middle은 start와 end를 더해 반으로 나눕니다. 리스트 중간쯤 위치하겠죠. 이때 비교를 한 번 하게 되고 target이 이 인덱스 값보다 크든 작든 이후에 비교해야 할 대상이 절반으로 줄어듭니다. 그렇다면 비교 대상이 절반씩 몇 번 줄어들어야 마지막 원소 하나만 남게 될까요? 이것을 바꾸어서 이야기하면 리스트 크기 n을 2로 몇 번 나누어야 1이 되느냐입니다. 이는 로그를 이용하면 됩니다.
log2n = num of division
이 알고리즘의 빅오는 O(log n)이 되지요. 여기에 조금 더 상상을 더해 봅시다. 이진 트리도 특별한 형태의 연결 리스트입니다. 부모는 두 자식의 참조를 가지고 있고 자식은 부모의 참조를 가지고 있습니다. 부모 노드만 쉽게 특정할 수 있다면, 새로운 노드를 삽입하거나 삭제하는 것은 부모 노드를 특정하는 알고리즘을 제외하고 O(1)이 됩니다. 여기에 트리가 어떤 기준에 따라 정렬되어 있다면 부모 노드를 찾는 것도 이진 탐색을 적용해서 O(log n)이 가능할 것 같습니다. 탐색이야 단순히 한 노드를 특정하는 것이니 당연히 O(log n)입니다. 데이터의 삽입과 삭제, 탐색 모두 O(log n)이 가능하다니 아주 멋진 발상입니다. 검색은 빠르지만 삽입과 삭제가 느린 동적 배열과 삽입과 삭제가 빠르지만 검색이 느린 연결 리스트의 단점을 완전히 보완할 수 있겠군요. 바로 이 트리가 이진 탐색 트리입니다.
이진 탐색 트리는 데이터의 삽입, 삭제, 탐색 외에도 여러 강력한 연산을 제공합니다. 또 딕셔너리(dictionary)를 구현하는 대표적인 자료 구조입니다. 딕셔너리라는 이름은 파이썬을 공부한 사람이라면 익숙한 용어이지요. 다음 절에서는 딕셔너리를 간단히 살펴보겠습니다.