컴퓨터 · 이진 탐색
100만 개의 이름 중 하나를 어떻게 20번 만에 찾을까요?
이 영상에서 볼 내용
전화번호부에 이름이 백만 개, 가나다순으로 있습니다. 하나씩 확인하면 백만 번을 봐야 할 수도 있습니다. 더 잘할 수 있을까요? 딱 한가운데를 펼쳐 보세요. 찾는 이름은 더 뒤에 있으니, 앞쪽 절반이 통째로 사라집니다. 남은 건 오십만 개. 남은 부분의 한가운데를 펼치고, 다시 반으로 줄입니다. 그리고 또. 한 번 볼 때마다 남은 것의 절반을 버립니다. 스무 번 반으로 나누면 백만이 하나로 줄어듭니다. 이의 이십 제곱이 백만을 조금 넘기 때문이죠. 이름이 십억 개라면요? 열 번만 더 보면 됩니다.
