스무고개로 백만을
백만 가운데 하나를 스무 번에 찾습니다
1부터 100만 사이의 수를 하나 마음속에 정하십시오. 제가 「그 수보다 큽니까?」만 물어서 맞히겠습니다. 몇 번이면 될까요.
스무 번입니다. 백만 번도, 천 번도 아닙니다. 한 번 물을 때마다 남은 것이 절반이 되기 때문입니다.
이야기
이 방법은 너무 자연스러워 보여서 누가 처음 썼는지 알 수 없습니다. 사전에서 낱말을 찾을 때 우리는 이미 이 방법을 씁니다. 가운데를 펴 보고, 앞이면 앞쪽 절반만, 뒤면 뒤쪽 절반만 봅니다.
그런데 이것을 컴퓨터 프로그램으로 옳게 적는 일은 뜻밖에 어려웠습니다. 1946년에 처음 발표된 뒤, 범위의 경계를 옳게 다룬 프로그램이 나온 것은 1962년이라고 「컴퓨터 프로그래밍의 예술」을 쓴 도널드 크누스가 적었습니다. 십육 년이 걸린 것입니다.
이야기는 거기서 끝나지 않습니다. 2006년, 자바 표준 라이브러리에 들어 있던 이진 탐색에서 버그가 발견됩니다. 가운데를 구할 때 로 적었는데, 두 수가 아주 크면 더하는 순간 넘쳐서 음수가 되었습니다. 구글의 조슈아 블로크가 「우리 모두가 쓰던 코드가 틀렸다」고 알렸습니다.
왜 스무 번이면 될까요. 한 번 물을 때마다 남는 것이 절반입니다. 백만 → 50만 → 25만 → … 로 줄어듭니다.
그러니 2를 몇 번 곱해야 백만이 넘나를 물으면 됩니다. 이므로 스무 번입니다. 제154장 에서 본 「몇 번 곱했나」가 바로 이것입니다.
사전 찾기, 데이터베이스 색인, 파일에서 한 줄 찾기, 게임에서 딱 맞는 난이도 찾기 — 모두 「반씩 줄이기」입니다. 미리 줄을 세워 두면 찾기가 놀랄 만큼 빨라집니다.
계단 넷 — 같은 사실을 네 깊이로
숫자 맞히기를 반씩 잘라 한다
친구에게 1부터 100 사이의 수를 하나 정하게 합니다. 그리고 「50보다 큽니까?」부터 물어보세요.
크다면 51~100, 작다면 1~49 만 남습니다. 한 번에 절반이 사라집니다. 다음에는 남은 것의 가운데를 물으세요.
몇 번 만에 맞혔나요? 일곱 번이면 충분합니다. 한 개씩 물었다면 백 번이 걸렸을 일입니다.
반씩 줄면 몇 번 만에 끝나나
한 번에 절반이 되므로, 개에서 시작해 번 물으면 개가 남습니다.
남은 것이 1이 되면 끝이니 , 곧 입니다.
백만이면 로는 모자라고 이면 넘으므로 스무 번입니다. 십억이면 서른 번, 조 단위여도 마흔 번입니다.
로그 시간과 정렬의 조건
걸리는 횟수는 입니다. 이것을 이라 적습니다.
그런데 조건이 하나 있습니다 — 줄이 서 있어야 합니다. 정렬되어 있지 않으면 「크다/작다」로 절반을 버릴 수가 없습니다. 한 번 찾자고 정렬하는 것은 손해지만, 여러 번 찾을 것이면 정렬해 두는 편이 훨씬 낫습니다.
가운데를 구할 때는 로 적습니다. 는 넘칠 수 있기 때문입니다.
비교로는 그보다 빨리 못 찾는다
이보다 빠를 수는 없을까요. 「크다/작다」만 물어서 찾는다면 없습니다. 증명은 셈으로 됩니다.
질문 하나에 답은 두 가지이므로, 번 물으면 구별할 수 있는 경우가 많아야 가지입니다.
가지를 구별하려면 이어야 하므로 — 아래로 막혀 있습니다. 정보이론의 첫 문장이 이것입니다.
물론 「크다/작다」가 아닌 다른 것을 물을 수 있다면 이야기가 달라집니다. 해시는 한 번에 찾고, 보간 탐색은 값의 분포를 이용합니다.
풀어 보기
반씩 줄이기.
(1) 1024개 가운데 하나를 이 방법으로 찾으면 최대 몇 번 물어야 하는가?
(2) 1부터 100만까지에서 최대 몇 번인가? 한 개씩 확인하는 것과 견주시오.
(3) 질문 한 번에 답이 「크다·작다·같다」 세 가지라면, 백만 가운데 하나를 최대 몇 번에 찾을 수 있는가?
답과 풀이 보기
(1) 10번입니다.
이므로 .
1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1 — 열 번 자릅니다.
(2) 20번입니다.
이므로 .
한 개씩 확인하면 최대 100만 번입니다. 5만 배 차이입니다.
⭐ 1초에 한 번씩 물으면 하나는 20초, 다른 하나는 11일이 넘습니다.
(3) 13번입니다.
답이 세 가지면 번에 가지를 가릅니다.
이므로 13번.
⭐ 제50장 의 가짜 동전이 바로 이 이야기입니다. 양팔저울의 답이 세 가지라 셋씩 나누는 것이 옳았습니다.
더 멀리
「반씩 줄이기」는 찾기 말고도 널리 쓰입니다.
- 답 구간 좁히기 — 방정식의 해를 구할 때 부호가 바뀌는 구간을 절반씩 좁혀 갑니다
- 병합 정렬 — 반으로 나눠 각각 정렬하고 합칩니다. 역시 가 나옵니다
- 버전 이분 탐색 — 프로그램이 언제부터 고장 났는지 찾을 때 고친 기록을 반씩 잘라 봅니다
이어지는 장
영감을 받은 곳
이진 탐색은 특정한 발견자가 알려져 있지 않은 오래된 방법입니다. 존 모클리가 1946년 무어 스쿨 강의에서 처음 언급한 것으로 전해지며, 도널드 크누스 『컴퓨터 프로그래밍의 예술』 제3권이 올바른 구현이 1962년에야 나왔다고 적고 있습니다. 2006년 자바 라이브러리의 오버플로 버그는 조슈아 블로크가 공개했습니다. 공개된 사실이며, 계단·문항·그림은 우리가 지었습니다.