이 구현은 1,024개 값을 최대 열한 번의 중간값 검사로 찾는다.
예제는 0부터 2,046까지 모든 짝수를 순서대로 담는다. 순차 검색은 하나씩 볼 수 있지만 이진 검색은 가운데부터 본다. 목표가 작다면 중간보다 뒤의 값은 모두 제외된다. 답 하나마다 남은 불확실성의 큰 부분을 버릴 권리를 얻는다.
정렬은 한 비교를 여러 항목에 대한 정보로 바꾼다.
정렬이 핵심 일을 한다
프로그램은 양끝을 포함하는 낮은 인덱스와 높은 인덱스로 시작한다. 가운데 값을 보고 목표와 같으면 위치를 반환한다. 작으면 오른쪽만, 크면 왼쪽만 남긴다. 이미 본 중간은 다음 후보에서 제외한다.
검색과 같은 비교 규칙으로 정렬돼 있어야 한다. 그렇지 않으면 목표보다 큰 값 하나로 그쪽의 다른 값에 대해 믿을 정보를 얻지 못한다. 핵심 약속은 아직 가능한 일치가 활성 구간 안에 남는다는 것이다.
열한 질문의 뜻
스크립트는 존재하는 1,024개 키를 각각 검색해 모든 반환 인덱스를 확인했다. 최대 열한 번, 목표를 같은 비중으로 평균하면 약 9.012번의 중간 탐색이었다. 일부는 첫 중간에서 찾고 다른 일부는 가장 깊은 결정 경로에 있다.
여기서 탐색 한 번은 중간값 하나를 읽고 살피는 것이다. 모든 Python 비교 명령, 메모리 접근, 시간 단위의 수가 아니다. 한 탐색 안에서 동일성과 대소를 차례로 검사할 수 있다. 단위를 밝히면 검색 깊이를 성능 벤치마크로 바꾸지 않고 이야기할 수 있다.
두 배면 대략 한 단계 더
중간값이 남은 후보의 절반가량을 제외하면 다음 질문은 더 작은 목록을 만난다. 반복하면 탐색 횟수는 로그 형태로 증가한다. 시험한 2의 거듭제곱 크기에서 최악의 성공 검색은 두 항목의 두 번에서 4,096항목의 열세 번까지 늘었다. 크기가 두 배일 때 최대가 하나 늘었다.
정확한 횟수에는 경계 규칙도 중요하다. 양끝을 포함하는 이 구현은 일부 경로에 마지막 검사가 하나 더 있어 “1,024개면 정확히 열 비교”라는 제목은 틀리다. 큰 증가 원리는 유지되지만 그림의 정확한 수는 실제 프로그램에서 얻어야 한다.
후보가 없음을 증명하기
없다는 경우도 다뤄야 검색이 완성된다. −1, 1, 2,048을 물었으며 앞의 둘은 열 번, 마지막은 열한 번 걸렸다. 낮은 인덱스가 높은 인덱스를 넘으면 후보 구간이 비고 정해 둔 실패 결과를 반환한다.
빈 입력은 중간 탐색이 0번이다. 구간을 제대로 줄이지 않으면 무한 반복이나 범위 밖 읽기가 생길 수 있어 이런 경계 검사가 중요하다. 중복 키는 별도 선택을 요구한다. 아무 일치, 처음, 마지막, 삽입 경계 중 무엇을 찾는가? 예제는 모두 다른 키라 모든 중복 정책을 해결하지는 않는다.
빠른 검색에는 준비 비용이 있다
무순서 자료를 정렬하는 데도 일이 들므로 한 번의 질문에 항상 이득은 아니다. 반복 조회라면 정렬 유지가 유용할 수 있지만 일반 배열에 삽입하면 많은 항목을 옮겨야 한다. Python bisect 문서도 빠른 경계 검색과 더 비싼 삽입을 구별한다.
중간에 직접 접근할 수 있어야 한다. 위치에 가려면 노드를 따라 걸어야 하는 연결 구조는 논리만 복사해 같은 총비용을 얻지 못한다. 정보 조직이 핵심이다. 믿을 만한 제외 규칙과 싼 접근을 갖춘 구조에서는 한 항목의 답으로 여러 후보를 지울 수 있다.
더 읽어 보기
Python: bisect and insertion complexity ↗Princeton: binary search implementation ↗공식 문서와 함께 읽으면 좋은 자료입니다.