이분 탐색은 정렬된 범위나 단조로운 판정 조건에서 후보 구간을 절반씩 줄이는 탐색 방법이다.
원리
중간 지점의 결과를 보고 해가 있을 수 없는 절반을 제외한다. 탐색 구간에 해가 포함된다는 불변식을 유지하며 경계와 종료 조건을 일관되게 정의한다.
예시
정렬된 값 2, 5, 8, 11, 14에서 11을 찾을 때 가운데 8과 비교하면 왼쪽 부분은 제외할 수 있다.
주의할 점
중복 값이 있으면 임의의 일치 위치, 첫 위치, 마지막 위치가 서로 다른 문제다. 빈 구간과 해가 없는 경우를 검사하고 중간값 계산의 정수 범위도 확인한다.