보통
Binary Search
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 binarySearch(nums, target):2 lo = 0, hi = n-1 // 탐색 구간3 반복 lo ≤ hi:4 mid = (lo + hi) / 2 // 가운데 인덱스5 만약 nums[mid] == target:6 반환 mid // 찾음7 만약 nums[mid] < target:8 lo = mid + 1 // 오른쪽 절반만 남김9 아니면:10 hi = mid - 1 // 왼쪽 절반만 남김11 반환 -1 // 없음
변수
- lo
- 0
- hi
- 6
- target
- 7
- n
- 7
1 / 4탐색 구간을 배열 전체 [0 … n-1]로 잡습니다.
정렬된 배열에서 매 단계 후보를 절반씩 버려 O(log n)에 찾는다.
왜 헷갈리는가
lo/hi 경계와 mid 갱신에서 무한 루프·off-by-one이 가장 자주 난다. 또 '정렬돼 있어야만' 성립한다는 전제를 잊고 아무 배열에 쓰려다 틀린다.
핵심 아이디어
불변식은 '답이 있다면 [lo, hi] 안에 있다'이다. 중앙값을 보고 목표와 비교해, 목표가 더 크면 왼쪽 절반을, 작으면 오른쪽 절반을 통째로 버린다.
매 비교가 후보를 절반으로 줄이므로 10억 개도 약 30번이면 끝난다.
복잡도
시간 O(log n), 공간 O(1)(반복형). 전제: 데이터가 정렬(또는 단조)돼 있어야 한다.
실무에서 어디에 쓰나
'단조성'만 있으면 값이 아니라 '조건'에도 이분 탐색을 건다(parametric search).
- DB 인덱스: B-tree/정렬 인덱스의 키 탐색이 사실상 이분 탐색
- 회귀 추적: git bisect로 버그가 처음 생긴 커밋을 O(log n)에 특정
- 시계열: 정렬된 타임스탬프에서 특정 시점 이상/이하 첫 지점 조회
- 용량 튜닝: '이 QPS를 견디는 최소 인스턴스 수' 같은 임계값 탐색
흔한 실수
mid = (lo+hi)/2는 큰 인덱스에서 오버플로 위험 → lo + (hi−lo)/2. 경계 갱신을 mid±1로 하지 않으면 무한 루프. '찾기'와 '경계(lower/upper bound)'를 섞지 않기.
기억할 것
- 정렬(단조)이 전제. 없으면 못 쓴다.
- 값뿐 아니라 '조건의 경계'에도 건다(parametric).
- mid는 lo+(hi−lo)/2, 경계는 mid±1.
- 10억을 30번에 — 로그의 힘.