어린 시절(혹은 지금 자신의 아이와) 다음과 같은 알아맞추기 게임을 해본 적이 있을 것이다. 한 사람이 1과 100 사이의 어떤 수를 머릿속으로 생각한다. 어떤 수를 생각하고 있는지 상대방이 맞춰볼 때마다 그 수보다 더 큰지 작은지 추측할 수 있도록 알려준다.

우리는 이 게임을 어떻게 해야 하는지 직관적으로 안다. 처음에 숫자 1을 고르는 일은 없을 것이다. 아마도 한가운데에 있는 50으로 시작할 것이다. 왜냐고? 50을 고르면 어떤 답이 나오든 가능한 수 중 반을 제거할 수 있기 때문이다!

50을 말했는데 더 크다고 알려주면 역시나 나머지 수 중 반을 없앨 수 있도록, 아마 다음으로 75를 고를 것이다. 75를 말했는데 더 작다고 알려주면 아마도 62나 63을 고를 것이다. 이런 식으로 계속해서 중간 지점을 골라 남은 수 중 반을 제거해 나간다.

1과 10 사이의 수를 맞춘다고 가정하고 이 과정을 그림으로 나타내 보자.

▲ 그림 2-11

이게 바로 이진 검색이다.