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

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

## 기타 등등

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

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