확인하지 않아도 버릴 수 있는 범위
번호가 작은 순서로 놓인 64개의 상자를 생각하자. 중간 상자의 번호가 목표보다 작으면 그 앞의 상자들도 목표가 될 수 없다. 비교 한 번으로 남길 범위를 좁히는 성질이 이진 검색의 핵심이다.
정렬 조건이 필요한 이유
중간값보다 작은 모든 값이 앞쪽에 있다는 보장이 없으면 절반을 제외할 수 없다. 따라서 비교에 사용하는 순서와 자료를 정렬한 기준이 일치해야 한다.
자료를 처음 정렬하는 비용과 검색 비용도 구분해야 한다. 한 번만 찾는 작은 자료에서는 정렬부터 하는 방법이 단순한 순회보다 불리할 수 있다.
값 찾기와 경계 찾기
목표값이 여러 번 나타날 때 아무 위치나 찾는 일과 첫 위치 또는 마지막 위치를 찾는 일은 다르다. 값을 발견한 뒤에도 조건에 맞는 경계를 향해 범위를 줄이는 변형을 사용한다.
마찬가지로 참과 거짓이 한 번만 바뀌는 단조 조건에서도 경계를 찾는 데 이 방법을 적용할 수 있다. 비교 결과로 어느 쪽을 제외할 수 있는지가 명확해야 한다.
효율과 구현 조건
반복할 때 후보 수를 대략 반으로 줄이므로 비교 횟수는 자료 크기의 로그에 비례한다. 다만 연결 리스트처럼 중간 위치에 접근하는 데 시간이 드는 구조에서는 전체 실행 시간의 해석이 달라진다.
범위의 양 끝을 포함하는지와 종료 조건을 일관되게 정해야 한다. 빈 범위와 중복값, 범위 끝의 목표를 빠뜨리지 않는 구현이 중요하다.