Ch.8 정렬과 탐색
Binary Search 변형 — lower bound, upper bound, rotated array
단순 검색을 넘어 '조건을 만족하는 경계'를 찾는다
시험 점수 배열에서 '70점 이상인 첫 번째 사람'을 찾고 싶습니다. 단순 Binary Search로는 안 됩니다.
target이 여러 개이거나 정확히 없을 때, lo와 hi를 어떻게 움직여야 하지?
lower bound와 upper bound 패턴을 익히면 거의 모든 Binary Search 변형을 풀 수 있습니다.
핵심 개념
Lower Bound
target 이상인 값이 처음 나타나는 위치
Upper Bound
target 초과인 값이 처음 나타나는 위치
핵심 내용
lower_bound: target 이상인 첫 번째 위치를 찾습니다
def lower_bound(arr, target):
"""target 이상인 값의 첫 인덱스"""
lo, hi = 0, len(arr)
while lo < hi: # 주의: < (등호 없음)
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # 주의: mid - 1이 아님
return lo
# 예시
arr = [1, 3, 3, 5, 7]
lower_bound(arr, 3) # → 1 (첫 번째 3의 위치)
lower_bound(arr, 4) # → 3 (4 이상인 첫 위치 = 5의 위치)기본 Binary Search와 차이: `while lo < hi` + `hi = mid` (mid - 1이 아님!)
upper_bound: target 초과인 첫 번째 위치를 찾습니다
def upper_bound(arr, target):
"""target 초과인 값의 첫 인덱스"""
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= target: # 유일한 차이: <= (등호 포함)
lo = mid + 1
else:
hi = mid
return lo
# 활용: target의 개수
arr = [1, 3, 3, 3, 5, 7]
count_3 = upper_bound(arr, 3) - lower_bound(arr, 3) # → 3lower/upper bound 활용: • target의 개수 = upper - lower • target이 존재하는지 = arr[lower] == target • 삽입 위치 = lower_bound
lower_bound와 upper_bound의 차이는 딱 한 글자: `<` vs `<=`
[4, 5, 6, 7, 0, 1, 2] 정렬된 배열이 회전되었습니다
회전 정렬 배열의 특징: • 어딘가에서 꺾이는 지점이 있음 • mid를 기준으로 한쪽은 반드시 정렬되어 있음 • 정렬된 쪽에 target이 있는지 판단 → 범위 좁히기
def search_rotated(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
# 왼쪽이 정렬된 경우
if arr[lo] <= arr[mid]:
if arr[lo] <= target < arr[mid]:
hi = mid - 1
else:
lo = mid + 1
# 오른쪽이 정렬된 경우
else:
if arr[mid] < target <= arr[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1핵심 통찰: mid 기준 정렬된 쪽을 먼저 확인하고, target이 그 범위에 있는지 판단합니다
[4,5,6,7,0,1,2]에서 target=0을 찾는 과정입니다
회전 배열에서도 O(log n)으로 탐색이 가능합니다
모든 Binary Search 변형은 3가지 패턴으로 귀결됩니다
패턴 1: 정확한 값 찾기 `while lo <= hi`, `return mid` 패턴 2: 경계 찾기 (lower/upper bound) `while lo < hi`, `hi = mid` or `lo = mid + 1` 패턴 3: 조건 만족하는 최솟값/최댓값 `while lo < hi`, 조건 함수로 판단
면접에서는 "어떤 패턴인지 먼저 판단"하고 코드를 작성하세요
arr = [1, 3, 3, 3, 5]에서 lower_bound(arr, 3)의 결과는?
회전 정렬 배열에서의 탐색은 O(n)이 최선이다
Binary Search 변형 완파!
정리 노트
Binary Search 변형
핵심 패턴
- lower_bound
- target 이상인 첫 위치 — `hi = mid`
- upper_bound
- target 초과인 첫 위치 — `<=` 비교
- rotated search
- 정렬된 쪽 먼저 판별 → 범위 좁히기
면접 팁
- target 개수
- `upper_bound - lower_bound`
- 패턴 선택
- 정확한 값 / 경계 / 조건 만족 — 3가지 중 판단
Binary Search 문제를 만나면 '어떤 패턴?'을 가장 먼저 결정하세요!
시각 자료
핵심 정리
- 1lower/upper bound — 경계 찾기 패턴
- 2Rotated array — 정렬된 쪽 판별이 핵심
- 33가지 패턴으로 모든 Binary Search 변형 대응
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작