이진 탐색 과정 계산기

원소가 n개면 최대 ⌈log₂(n+1)⌉번 비교합니다. 원소가 1,000개면 10번, 100만 개면 20번입니다. 한 번 볼 때마다 후보가 절반으로 줄기 때문이며, 이것이 앞에서부터 하나씩 보는 선형 탐색(최대 n번)과의 차이입니다. 다만 찾는 값이 목록 맨 앞에 있다면 선형 탐색이 한 번 만에 끝나므로, 이진 탐색이 언제나 적게 보는 것은 아닙니다.

있는 값을 「없다」고 답할 수 있습니다. 이진 탐색은 「가운데 값보다 크면 오른쪽에 있다」는 전제로 절반을 버리는데, 정렬되어 있지 않으면 그 전제가 깨져 버린 쪽에 답이 있을 수 있습니다. 오류를 내지 않고 조용히 틀리기 때문에 더 위험하며, 이 계산기는 정렬 여부를 먼저 검사해 알려 줍니다.

low + high가 정수 최댓값을 넘으면 오버플로가 나 음수가 되기 때문입니다. mid = low + (high − low) / 2로 쓰면 이 문제가 없습니다. 자바 표준 라이브러리의 이진 탐색에 이 버그가 9년 동안 있다가 2006년에야 고쳐진 일이 유명합니다. 자바스크립트는 수가 2의 53제곱까지 안전해 실제로 터지지는 않지만, 안전한 식으로 적어 두는 편이 좋습니다.

그 값을 끼워 넣을 자리를 알려 줍니다. low와 high가 엇갈리며 멈출 때의 low가 그 자리이며, 여기에 값을 넣으면 정렬이 그대로 유지됩니다. C++의 lower_bound, 파이썬의 bisect_left가 돌려주는 값이 바로 이것입니다.

고전 이진 탐색은 그중 아무 자리나 돌려줍니다. 어느 것을 먼저 만나느냐가 배열 크기에 따라 달라지기 때문입니다. 첫 자리가 필요하면 lower_bound를, 마지막 다음 자리가 필요하면 upper_bound를 써야 하며, 두 값을 빼면 그 값이 몇 개인지 알 수 있습니다. 이 계산기는 셋을 모두 보여 줍니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.