가운데 값으로 후보 줄이기
오름차순 자료의 가운데 값보다 찾는 값이 작다면 그보다 큰 쪽은 후보에서 제외할 수 있다. 반대이면 작은 쪽을 제외한다. 범위를 줄일 수 있는 이유는 자료가 비교 기준에 맞게 정렬되어 있기 때문이다.
정렬되지 않은 자료에서는
자료의 배치에 순서가 없다면 가운데 값 하나를 보고 반대편에 답이 없다고 판단할 수 없다. 정렬되지 않은 입력에 이진 탐색을 적용하면 존재하는 값을 놓칠 수 있다. 탐색 전에 필요한 정렬 비용과 이미 정렬된 자료를 반복 조회하는 상황도 구분해야 한다.
중복 값과 경계
같은 값이 여러 개라면 발견한 하나의 위치와 가장 앞이나 뒤의 위치는 다를 수 있다. 원하는 결과가 무엇인지에 따라 같을 때도 탐색을 계속할 방향을 정한다. 후보가 비었을 때의 종료 조건과 경계 포함 여부도 일관되게 다뤄야 한다.
비교 횟수와 접근 비용
배열에서는 가운데 원소를 바로 읽기 쉽지만 연결 구조에서는 그 위치까지 이동하는 비용이 들 수 있다. 따라서 비교 횟수가 적다는 사실이 모든 자료 구조에서 같은 전체 시간을 보장하지 않는다. 원소 접근 방식까지 포함해 비용을 따져야 한다.