탐색 기법O(log n)

이분탐색 — 값·경계 찾기

정렬돼 있으면 절반씩 버려요. 100만 개도 20번이면 끝나요.

이럴 때 써요

정렬된 배열에서 특정 값이 있는지, 어디 있는지 찾을 때
값이 없을 때 어디에 끼워 넣어야 정렬이 유지되는지 (삽입 위치) 묻는 문제
"~보다 크거나 같은 첫 번째", "~보다 작은 마지막" 같은 경계를 찾을 때
입력이 100만 개 넘어서 O(n)으로도 빠듯한데 데이터가 정렬돼 있을 때

개념

정렬돼 있으면 가운데를 딱 한 번 보는 것만으로 절반을 통째로 버릴 수 있어요. mid가 target보다 크면 오른쪽은 볼 필요도 없고, 작으면 왼쪽을 버려요. 한 번에 후보가 반으로 줄어드니 100만 개도 log₂(1,000,000) ≈ 20번이면 끝나요. 대신 정렬이 전제예요. 안 돼 있으면 먼저 정렬해요.가장 헷갈리는 건 구간 경계예요. 여기선 lo와 hi를 양끝을 포함하는 닫힌구간 [lo, hi]로 잡을게요. 그래서 조건이 while (lo <= hi)(같을 때도 검사)이고, 버릴 땐 검사한 mid를 확실히 빼내려고 lo = mid + 1 / hi = mid - 1로 한 칸씩 넘겨요. 이 셋이 짝이 맞아야 무한 루프에 안 빠져요.

"정렬된 [1, 3, 5, 7, 9, 11]에서 7 찾기" — 닫힌구간 [lo, hi]
값:  1  3  5  7  9  11
칸:  0  1  2  3  4   5
lo=0, hi=5  →  mid=2, a[2]=5  <  7  →  왼쪽 버려요, lo=3
lo=3, hi=5  →  mid=4, a[4]=9  >  7  →  오른쪽 버려요, hi=3
lo=3, hi=3  →  mid=3, a[3]=7  =  7  →  찾았어요! 칸 3 반환

값이 없을 땐 "있냐 없냐" 대신 "어디 끼워야 하나"를 물어요. 이게 lower bound(삽입 위치) 예요. target 이상인 첫 칸을 찾는 건데, 요령은 조건을 만족하는 mid를 만나면 그 자리를 답 후보로 기억(hi = mid)하고 왼쪽으로 더 밀어보는 거예요. 없으면 배열 끝(n)이 답이라, target이 최댓값보다 커도 자연스럽게 맨 뒤 자리를 가리켜요.

묻는 것	찾는 자리	target이 없으면
값이 있나?	일치하는 아무 칸	`-1` 반환
lower bound	`target` 이상인 첫 칸	끼워 넣을 자리(맨 뒤 포함)

패턴 코드

기본 이분탐색 — 값이 있으면 그 칸, 없으면 -1lo와 hi로 닫힌구간 [lo, hi]를 잡아요. while (lo <= hi)로 한 칸짜리 구간까지 검사하고, 버릴 땐 mid를 확실히 넘겨요.

javascript
Copy code
function binarySearch(arr, target) {
  let lo = 0;
  let hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

삽입 위치 (lower bound) — target 이상인 첫 칸여긴 반열린구간 [lo, hi)를 써요. hi를 n에서 시작해 조건을 만족하면 hi = mid로 답을 좁히고, 못 찾으면 lo가 맨 뒤(n)를 가리켜요.

javascript
Copy code
function lowerBound(arr, target) {
  let lo = 0;
  let hi = arr.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

이 유형으로 풀어보기

← 상위 K개·K번째 수 — 우선순위 큐 파라메트릭 서치 — 결정 문제로 바꾸기 →