무엇을 찾는지 먼저 정하기
값 하나가 존재하는지, 같은 값들 가운데 처음 위치가 어디인지, 특정 값보다 큰 첫 위치가 어디인지는 다른 문제다. 중간값이 목표와 같다고 곧바로 종료하면 첫 위치를 찾는 요구에는 맞지 않을 수 있다. 탐색 전에 답의 의미를 문장으로 정한다. 구간을 줄이는 규칙은 그 의미를 계속 보존해야 한다.
포함하는 끝과 제외하는 끝
구간을 왼쪽 끝은 포함하고 오른쪽 끝은 제외하는 방식으로 표현하면 두 끝이 같은 경우를 빈 범위로 해석할 수 있다. 양 끝을 모두 포함하는 방식도 가능하지만 갱신과 종료 조건을 그 정의에 맞춰야 한다. 두 표현의 식을 섞으면 마지막 후보를 건너뛰거나 같은 구간을 반복하기 쉽다. 매 단계 남은 후보가 실제로 줄어드는지 확인한다.
중복값의 두 경계
정렬된 자료 2, 4, 4, 4, 9에서 4를 넣을 왼쪽 경계는 0부터 센 위치 1이고 오른쪽 경계는 4다. 왼쪽 경계는 4보다 작은 값들의 뒤이며 오른쪽 경계는 4 이하 값들의 뒤다. 이 차이를 이용하면 같은 값의 범위도 구할 수 있다. 다만 삽입 위치가 나왔다는 사실만으로 그 값이 실제로 존재한다고 판단하지 않는다.
존재하지 않는 값
모든 값보다 작은 값을 찾으면 경계가 맨 앞일 수 있고 모든 값보다 큰 값을 찾으면 맨 뒤의 제외 경계일 수 있다. 결과를 배열 원소처럼 바로 읽으면 범위를 벗어날 수 있으므로 위치의 유효성을 먼저 확인한다. 빈 배열과 원소 하나의 배열도 같은 규칙으로 동작하는지 검사하면 경계 오류를 좁히기 쉽다.
탐색 뒤의 작업 비용
정렬된 배열에서 위치를 찾는 비용과 그 자리에 원소를 넣는 비용은 다르다. 위치 탐색이 빠르더라도 삽입을 위해 많은 원소를 이동해야 할 수 있다. 반복 삽입이 주된 작업이라면 전체 비용을 따로 평가한다. 이진 탐색을 사용했다는 사실만으로 이후의 모든 연산이 로그 시간이라고 말할 수는 없다.
관련 문서
이진 탐색 / 알고리즘 / 성능 비교 실험 설계