같은 문제에 적용한 서로 다른 알고리즘에서 얼마나 효율성이 다르게 나타나는지 알아보기 위해 간단한 게임을 해보기로 합시다. 컴퓨터는 1에서 16까지의 정수 중 무작위로 하나를 선택합니다. 여러분은 컴퓨터가 고른 수를 알아낼 때까지 계속 그 수를 추측해야 합니다:
수를 찾았다면, 말해보세요. 어떤 방법을 이용해서 다음의 수를 추측했나요?
1을 고르고 2, 3, 4 를 고르는 방식으로 맞을 때까지 했을 수도 있을 겁니다. 이렇게 찾는 방법은 숫자들을 줄지어 있는것처럼 차례대로 검색하기 때문에 선형 검색(linear search)이라고 합니다. 꽤 확실한 방법이죠. 하지만 얼마나 많이 추측을 해야 할까요? 컴퓨터가 30을 고르게 되면 여러분은 30번이나 추측을 해야 합니다. 또한 정말 운 좋게도 컴퓨터가 1을 골랐다면 첫 번째 추측에서 숫자를 맞출 수 있겠죠. 평균적으로는 어떨까요? 컴퓨터가 1에서 30까지의 수를 고를 확률이 같다면 평균은 15번일 것입니다.
그렇지만 단순히 1, 2, 3, 4,..., 처럼 일일이 추측하는 방법보다 더 효율적인 방법이 있을 겁니다. 그렇죠? 컴퓨터가 추측한 값이 큰지 작은지 얘기해 주니까 15부터 시작할 수 있습니다. 컴퓨터가 고른 숫자가 15보다 작다면 15가 너무 크다는 것을 알기 때문에 15에서 30까지의 수는 고려 대상에서 제외할 수 있습니다. 컴퓨터가 고른 숫자가 15보다 크다면 1에서 15까지의 수를 제외할 수 있습니다. 어느 쪽이든 숫자 범위의 반을 제외할 수 있겠죠. 다음번 추측에도 남아있는 숫자들중에서 가운데 있는 수를 제거합니다. 이런 식으로 남아있는 숫자의 절반을 계속 제외합니다. 이런 방법을 이진 탐색(binary search)이라고 하는데 이 방법으로는 컴퓨터가 1부터 30중에 무슨 수를 고르던 최대 다섯 번의 추측안에 수를 맞출 수 있습니다.
1에서 300까지의 수로도 한 번 해 보세요. 최대 아홉 번의 추측이면 맞출 수 있을 겁니다.
이번에는 수를 맞추는데 몇 번이나 필요했나요? 아홉 번 이상의 추측이 필요하지 않은 이유는 뭘까요? (수학적으로 설명할 수 있나요)?
이진 검색법으로 돌아가서 JavaScript 배열에서 특정 항목을 어떻게 효율적으로 검색할지 알아보겠습니다. 그전에 먼저, 조금 더 어려운 문제를 해결하기 위한 알고리즘을 살펴보겠습니다.

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