이진 검색 실행 시간

$n$‍개의 요소가 있는 배열에서 선형 탐색으로 탐색을 하면 최대 $n$‍번의 탐색을 거쳐야 합니다. 아마 직관적으로 이진 탐색으로 훨씬 빨리 탐색을 할 수 있을거라는 생각이 들겁니다. 배열의 길이가 증가할수록 선형 탐색과 이진 탐색의 속도 격차는 더더욱 벌어집니다. 이진 탐색의 최대 탐색수를 알아보고 이를 분석하는 법을 배워 봅시다.

여기서 핵심 개념은 다음과 같습니다. 이진 탐색에서는 기준값과 배열의 정중앙에 있는 데이터를 비교하여 맞지 않을 경우 배열에 있는 기준값과 일치하지 않는 다른 쪽에 있는 값들은 모두 버립니다. 따라서 남은 값들에 대한 탐색을 다시 시작할 때 옳은 값을 찾을 확률은 이전 탐색에 비해 최대 두 배가 올라갑니다. 예를 들어 어떤 32개의 데이터가 있다고 가정해봅시다. 정렬된 데이터 중간의 어떤 값 하나를 비교해 보았더니 찾는 값보다 더 커서 이 값보다 큰 값들을 모두 버렸습니다. 그럼 남은 16개의 더 작은 값 중에서 탐색을 다시 시작하여 원하는 값을 찾게 됩니다. 이처럼 이진 탐색은 비교값이 틀릴 때마다 값의 범위를 반으로 줄입니다.

만일 길이가 8인 배열에서 탐색을 시작하여 비교값이 틀리면 다시 4개의 값에서 탐색하고 다음으로 2, 1 순으로 줄여나갑니다. 탐색하는 배열 안에 값이 한 개만 남아있으면 비교값과 일치 여부에 상관없이 탐색은 종료됩니다. 따라서 길이가 8인 배열의 경우 이진 탐색은 최대 네 번 탐색을 합니다.

그렇다면 배열에 값이 16개 있을 경우에는 어떻게 될까요? 첫 번째 탐색이 최소 8개의 값을 제외시켜서 남는 8개의 값에 대해 탐색을 한다고 생각했다면 이해를 올바르게 하고 있는 것입니다. 따라서 16개의 값을 가지는 배열에서는 탐색을 최대 5번만 하면 됩니다.

지금쯤이면 슬슬 규칙이 보이기 시작할 겁니다. 배열이 두 배 커질때마다 최대 탐색 횟수는 한 번 늘어납니다. 길이가 $n$‍인 배열에 최대 $m$‍ 번 만큼의 탐색이 필요하다고 가정해봅시다. 그렇다면 길이가 $2n$‍인 배열에서는 첫 번째 탐색을 한 다음 탐색 범위가 $n$‍ 으로 절반이 되므로 최대 $m$‍ 번의 탐색만 하면 원하는 값을 받드시 찾게됩니다. 따라서 이 경우 최대 $m+1$‍ 번의 탐색이 필요합니다.

길이가 $n$‍인 배열의 경우에 최악의 경우 추측 횟수는 $n$‍에서 시작해 1에 이르기까지 반복적으로 반으로 나누는 횟수 더하기 1이라고 할 수 있습니다. 하지만 이것을 말로 쓰기엔 불편합니다.

다행히 $n$‍에서 시작해 1에 이르기까지 반복적으로 반으로 나누는 횟수를 뜻하는 수학 함수가 존재합니다. 바로 2를 밑으로 하는 $n$‍의 로그입니다. 이는 보통 ${\log }_{2}n$‍이라고 쓰지만 컴퓨터 과학에서는 $\lg n$‍이라고 쓸 때도 있습니다. (로그에 대해 더 알고 싶다면 여기를 살펴보세요.)

아래 표는 2를 밑으로 하는 $n$‍의 로그함수 값 중 일부입니다:

이 표를 그래프로 나타낼 수도 있습니다:

n 값의 범위를 줄여서 그래프를 확대해 보겠습니다:

로그함수는 매우 천천히 증가합니다. 로그함수는 매우 빠르게 증가하는 지수함수와 역의 관계에 있습니다. 로그함수가 ${\log }_{2}n=x$‍라면 그에 대응하는 지수함수는 $n=2^x$‍입니다. 예를 들어 ${\log }_{2}128=7$‍이라면, $2^7=128$‍이라고 알 수 있습니다.

$n$‍이 2의 제곱일 때 이진 검색 알고리즘의 실행 시간을 계산하는 것은 간단합니다. $n$‍이 128이라면, 이진 검색은 최대 8(${\log }_{2}128+1$‍)번의 추측만 있으면 됩니다.

$n$‍이 2의 제곱이 아니라면 어떨까요? 그런 경우 n보다 낮은 가장 가까운 2의 제곱인 수를 고르면 됩니다. 길이가 1000인 배열이 있다면, n보다 낮은 가장 가까운 2의 제곱은 512($2^9$‍)입니다. 따라서 ${\log }_{2}1000$‍은 9와 10 사이라고 추측할 수 있고, 실제로 계산해보면 9.97 정도입니다. 여기에 1을 더하면 10.97이고, 소수가 나오는 경우 정수로 내림합니다. 따라서 1000개의 요소를 가진 배열을 이진 검색할 때는 최대 10번의 추측만 필요합니다.

항성 2,539,913개를 가진 Tycho-2 항성 목록의 경우 가장 가까운 2의 제곱은 $2^{21}$‍ ( 2,097,152)이므로, 최대 22번의 추측이 필요합니다. 선형 검색보다 훨씬 낫습니다.

다음은 $n$‍과 ${\log }_{2}n$‍를 비교한 그래프입니다:

다음 튜토리얼에서는 컴퓨터 과학자들이 선형 검색과 이진 검색의 실행 시간 중 가장 중요한 부분만을 추려내고 덜 중요한 부분을 없애는 방법을 통해 실행 시간의 특징을 어떻게 정의하는지 알아보게 될 것입니다.

위 자료는 다트머스 대학교 컴퓨터공학과의 토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.