토픽 17 / 82

이진 검색 (Binary Search)

정렬된 배열에서 중간 값과 비교하여 탐색 범위를 절반씩 줄여가며 목표 값을 찾는 분할 정복 기반 검색 알고리즘

목적: 빠른 검색(O(log n)), 정렬된 데이터

특징: 분할 정복, 정렬 필수, O(log n), 임의 접근 필요

동작: ① left=0, right=n-1 → ② mid = (left+right)/2 → ③ arr[mid] == target: 반환, < target: left=mid+1, > target: right=mid-1 → ④ 반복

시간 복잡도: 최선 O(1) - 중간 값, 평균·최악 O(log n)

공간 복잡도: O(1) - 반복, O(log n) - 재귀

오버플로우 방지: mid = left + (right - left) / 2

장점: 빠름(O(log n)), 효율적, 대규모 데이터

단점: 정렬 필요, 임의 접근 필요(연결 리스트 불가), 삽입·삭제 비효율

변형: Lower Bound(target 이상 첫 위치), Upper Bound(target 초과 첫 위치)

적용사례: 정렬 배열 검색, 데이터베이스 인덱스, 라이브러리 함수(bsearch)

비교: 이진(O(log n)/정렬필요) vs 선형(O(n)/정렬불필요) vs 해시(O(1)/정렬불가)

연관: 분할 정복, 정렬, BST, Lower/Upper Bound