binary search는 어떻게 동작하며 무엇을 필요로 하나요?

Question

Accepted Answer

**Binary search**는 **정렬된** 배열에서 검색 범위를 반복적으로 절반으로 줄여 가며 목표 값을 찾습니다. 각 비교가 남은 원소의 절반을 제거하므로 **O(log n)** 시간이 걸립니다. ## 개념 가운데 원소를 봅니다. 목표 값과 같으면 끝입니다. 목표 값이 더 작으면 왼쪽 절반을, 더 크면 오른쪽 절반을 검색합니다. 찾거나 범위가 비워질 때까지 반복합니다. ## 예시 ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # 가운데 인덱스 if arr[mid] == target: return mid # 찾음 elif arr[mid] < target: lo = mid + 1 # 왼쪽 절반 버림 else: hi = mid - 1 # 오른쪽 절반 버림 return -1 # 없음 binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## 추적 ```text [1,3,5,7,9]에서 7 검색 lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## 복잡도 - **시간:** O(log n). **공간:** 반복 구현 시 O(1). ## 함정 **입력은 반드시 정렬되어 있어야** 합니다 — 그렇지 않으면 결과가 무의미합니다. `lo`/`hi`의 off-by-one 버그와 일부 언어에서의 정수 오버플로(`lo + (hi-lo)//2` 사용)를 주의하세요. ## 왜 중요한가 검색 공간을 절반으로 줄이면 백만 개 원소의 조회가 약 20번의 비교로 바뀝니다. 그 배경에 있는 분할 정복 패턴은 트리, 데이터베이스, 그리고 수많은 면접 문제에서 다시 등장합니다. 유일하게 까다로운 요구 사항인 정렬된 입력을 아는 것은 고전적이고 미묘한 버그를 피하게 해 줍니다.