이진 탐색(binary search)은 정렬된 데이터에서 가운데 값을 비교하고 찾을 범위를 반복해서 절반으로 줄이는 알고리즘이다. 찾는 값과 정렬 기준이 맞아야 한다. (NIST 이진 탐색 사전)

• 가운데 값보다 작으면 앞쪽, 크면 뒤쪽을 남기는 식으로 범위를 좁힌다. 정렬되지 않은 데이터에서는 이 판단으로 후보를 버릴 수 없다. (이진 탐색의 정의)
• 임의 위치에 바로 접근할 수 있는 정렬 배열에서 탐색 시간은 O(log n)이다. 자료를 먼저 정렬하는 비용까지 없어지는 것은 아니다. (이진 탐색의 성능)
• 구현할 때는 범위 끝을 포함하는지와 다음 범위를 어디서 시작할지 일관되게 정한다. 가운데를 계산하는 정수 연산에는 정수 오버플로도 고려한다. (가운데 위치 계산의 주의점)

기타 등등

• NIST는 같은 방식으로 정렬된 연결 리스트를 탐색할 때 비교 횟수는 적어도 이동 횟수는 선형으로 늘어날 수 있다고 설명한다. 출처
• 양 끝 위치가 음수가 아닐 때 low + (high - low) / 2 형태는 두 큰 위치 값을 먼저 더하는 방식의 오버플로를 피할 수 있다. 출처

#알고리즘 #검색 #프로그래밍