[알고리즘] 이분탐색

이진 탐색이란?

• 핵심 정의
  • 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 찾는 알고리즘
  • 이때, 데이터가 반드시 정렬되어 있어야 한다
  • 예시) 1~ 100 사이 숫자를 맞출 때 “50보다 커?” 라고 묻는 것
• 동작 방식
  1. 중간값 선택
  2. 비교: 찾고자 하는 값(Target)과 비교
     • Target == 중간값: 탐색 종료
     • Target < 중간값: 왼쪽 절반을 새로운 범위로 설정
     • Target > 중간값: 오른쪽 절반을 새로운 범위로 설정
  3. 반복: 값을 찾거나 범위가 남지 않을 때까지 반복
• 시간 복잡도
  • O(\log n)
  • 한 번 시행할 때마다 남은 데이터의 개수가 1/2로 줄어듦
  • 데이터 개수가 n개일 때, k번 시행하면 남은 데이터는 $\frac{n}{2^k}$개가 됨
  • 최악의 경우 데이터가 1개 남을 때까지 탐색하므로, $\frac{n}{2^k} = 1$이 되는 시점을 찾으면 됨
  • 즉, n = 2^k이므로 k = log_2 n이 됨
  • 따라서 시간 복잡도는 O(log n)임

이진 탐색과 순차 탐색

적은 시간 복잡도 때문에 이진 탐색이 무조건 유리하다고 생각할 수 있지만, 정렬 비용 때문에 순차 탐색이 유리한 경우도 있다.

• 순차 탐색
  • 데이터가 정렬되어 있지 않을 때
  • 데이터의 양이 매우 적을 때
  • 예) 데이터가 수시로 추가/삭제되는 경우
• 이진 탐색
  • 데이터가 이미 정렬되어 있을 때
  • 한 번 정렬해두고 수만 번 검색할 때
  • 즉, 한 번 정렬해두면 찾는 건 매우 빠르게 가능함
  • 예) 고정된 데이터에서 검색만 하는 경우

응용

모든 이진 탐색 문제는 lower, upper bound를 이용해서 풀이 가능하다

처음 이해할 때는 일반적인 경우로 이해하고, 그 다음에 범위를 기반으로 문제를 풀어보자

 

• 일반적인 이진 탐색
  • 배열에 원하는 숫자가 있는지 찾고, 그 인덱스를 구하는 문제
  • 종료 조건: while (low ≤ high)
  • 범위: low = 0, high = v.size() - 1
  • 업데이트:
    • mid == target 이면 바로 return
    • 아니라면 mid + 1, mid - 1로 중간값을 건너뛴다
    • low와 high가 교차될 때까지 못 찾으면 없음을 반환한다배열 안의 인덱스만 찾으면 되기 때문이다
    • low > high가 되면 자동으로 “배열 전체를 봤는데 없네” 하고 끝난다
    • → high의 최대 범위는 v.size() - 1이다
• lower_bound, upper_bound
  • 중복이 있거나 경계를 찾을 때 사용
  • 30이 시작되는 곳(lower) 또는 30을 초과하는 곳(upper)를 찾을 때 쓴다
  • 조건문: while(low + 1 < high)
  • 범위: low = -1, high = v.size()
  • → 모든 값이 범위보다 크거나 작을 수도 있으므로 초과한 범위로 탐색한다
  • 업데이트:
    • high = mid 를 이용해 mid를 범위에 포함→ high의 최대 범위는 v.size()이다
    • → mid가 경계선일 수도 있기 때문
  • 특징
    • low == high가 되는 순간 멈추고, 그 지점이 경계선임
• 최적화 문제
  • 최적화 문제란 어떤 조건$(Check(x))$을 만족하는 $x$의 최댓값 또는 최솟값을 찾는 문제를 말한다
  • 이 경우 $Check(x)$가 $x$에 대해 이분적이면 이분 탐색을 사용할 수 있다
  • 예) F와 T의 경계선 찾기
    • 상황 가정라는 질문에 대해 데이터가 정렬되어 있다면 결과는 다음과 같다우리의 목표는 F가 끝나고 T가 시작되는 경계를 찾는 것이다
    • $[ 50kg(F), 60kg(F), 70kg(F), 80kg(T), 90kg(T), 100kg(T) ]$
    • 어떤 조건 Check()가 있다고 했을 때, *"몸무게가 $x$ 이상이면 과체중인가?"*
    • 핵심 로직 풀이
      • 시작할 때 lo는 확실한 오답(F)인 지점에, hi는 확실한 정답(T)인 지점에 둠
      • 그래야 그 사이에 '경계선'이 있다는 것이 보장되기 때문
      • ② "Check(lo) == Check(mid)라면 lo = mid, 아니라면 hi = mid"
      • 중간값 mid를 검사함
      • 만약 mid도 lo처럼 F → "경계선은 mid보다 오른쪽에 있네!" 하고 lo를 mid로 옮김
      • 만약 mid가 T → "경계선은 mid보다 왼쪽에 있네!" 하고 hi를 mid로 옮김
      • ③ "lo + 1 == hi가 되면 탈출"
      • 이 과정이 반복되면 lo와 hi는 점점 서로에게 다가감
      • 결국 lo는 마지막 F에, hi는 첫 번째 T에 딱 붙게 됨
      • 이때 둘의 인덱스 차이는 정확히 1이 됨 (lo + 1 == hi)
      • 더 이상 쪼갤 mid가 없으니 여기서 끝냄
    • ① "Check(lo) != Check(hi)가 되도록 잡음"

코드 예시

int lo = -1;        // 확실한 False (조건 만족 X)
int hi = v.size();  // 확실한 True 후보 (조건 만족 O)

while (lo + 1 < hi) {
    int mid = lo + (hi - lo) / 2;
    if (v[mid] >= target) { // [조건] 이 부분이 핵심!
        hi = mid; // True 영역을 확장 (hi 성벽 이동)
    } else {
        lo = mid; // False 영역을 확장 (lo 성벽 이동)
    }
}
// 결과: hi는 조건을 만족하는 '최소 인덱스'가 됨

• 배열에서 숫자가 존재하는지 찾기
• 배열에서 숫자가 몇 개 존재하는지 찾기
• 배열에서 조건을 만족하는 최솟값/최댓값 찾기

문제 예시

• 1654번: 랜선 자르기
  • 이분 탐색을 응용하여 최솟값이나 최댓값을 찾는 테크닉을 배우는 문제
  • 문제 풀이
    • 잘못된 접근법
      • 최솟값, 최댓값 범위를 정하는 과정에서 잘못된 생각을 했다
      • 최솟값이 1에서 시작해서, +1씩 증가하며 2, 3, 4.. 등 브루트포스적 사고를 했다 (시간초과)
      • 사실 low, high는 조건에 따라 계속 다음 mid 값으로 건너뛰므로 그렇게 동작하지는 않는다
      • ⇒ 그래서 우리는 범위를 절반씩 뚝뚝 잘라나가는 이분 탐색을 쓰는 거다!
    • 옳은 접근법
      • 최솟값, 최댓값
        • 주어진 숫자 배열 중 탐색해야 하므로, 처음 최솟값은 1, 처음 최댓값은 최대길이로 한다
• 1300번: K번째 수
  • 줄세운 배열에서 K번째 수에 어떤 값이 들어있는지 찾는 문제