노트

이진 탐색

Binary Search

CS#algorithm · 연결된 개념 6개

쉽게 말하면

이진 탐색은 업다운 숫자 맞히기 게임이에요. 가운데 숫자를 부르고 '업'이면 아래 절반을 통째로 버리니까, 100만 개 중에서도 20번 남짓이면 찾아요.

비유가 깨지는 곳 게임에서는 숫자가 이미 순서대로 놓여 있지만, 실제 배열은 정렬부터 해야 해요. 한 번만 찾을 거면 정렬 비용이 선형 탐색보다 커서, 여러 번 찾을 때 이득이에요.

정렬된 배열에서 가운데 값과 찾는 값을 비교해 매번 절반을 버리며 찾는 방법. 원소가 100만 개여도 20번 남짓이면 끝난다(O(log n)). 처음부터 하나씩 확인하는 선형 탐색(Linear Search)은 O(n)이다.

function binarySearch(arr: number[], target: number) {
  let lo = 0
  let hi = arr.length - 1
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2)
    if (arr[mid] === target) return mid
    if (arr[mid] < target) lo = mid + 1
    else hi = mid - 1
  }
  return -1
}
  • 정렬이 전제다. 한 번만 찾는다면 정렬 비용(O(n log n))이 선형 탐색보다 크다. 여러 번 찾을 때 이득이다
  • 경계 실수(<와 <=, mid ± 1)가 가장 흔한 버그다. 원소 0개·1개·2개로 꼭 확인한다
  • "조건을 처음 만족하는 위치 찾기"로 일반화하면 정답 값의 범위를 탐색하는 문제(파라메트릭 서치, Parametric Search)에도 쓴다
  • 같은 원리가 이진 탐색 트리와 DB 인덱스의 B-트리(B-Tree)에도 있다(DB 인덱스와 트레이드오프)
  • git bisect는 커밋 이력에 대한 이진 탐색이다(git bisect로 원인 커밋 찾기)

이진 탐색은 분할 정복의 가장 단순한 예다. 비교 삼아, 긴 문자열 안에서 짧은 문자열을 찾는 단순 문자열 탐색(Naive String Search)은 위치마다 한 글자씩 대조하는 O(n·m) 방법이다. 복잡도 감각은 빅오 표기법 참고.

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • 정렬 알고리즘

    컬렉션의 원소를 어떤 순서(크기, 사전순, 날짜…)로 다시 배치하는 알고리즘. 같은 일을 하는 방법이 여럿이고 각자 강점이 달라, 트레이드오프를 익히기 좋은 주제다.

  • 이진 힙

    부모가 항상 자식보다 크거나(최대 힙, Max Heap) 작은(최소 힙, Min Heap) 완전 이진 트리(Complete Binary Tree). 형제끼리의 순서는 정하지 않는다. 가장 크거나 작은 값이 항상 루트에 있어 꺼내기 쉽다.

  • 투 포인터

    배열이나 문자열에서 위치를 가리키는 포인터 두 개를 두고, 조건에 따라 움직여 가며 답을 찾는 패턴. 추가 메모리 없이(O(1) 공간) 중첩 반복을 한 번의 순회로 줄인다. 보통 정렬된 입력에서 쓴다.

  • 빈도수 세기 패턴

    값이 몇 번 나오는지를 객체나 Map에 모아 두고 비교하는 풀이 패턴. 배열이나 문자열끼리 비교할 때 생기기 쉬운 중첩 반복 O(n²)을 O(n)으로 줄인다.

  • 병합 정렬

    배열을 원소 하나가 될 때까지 반으로 나눈 뒤, 정렬된 조각 둘을 하나로 합치기를 반복하는 정렬. 원소 하나짜리 배열은 이미 정렬돼 있다는 점에서 출발한다. 분할 정복의 대표 예다.

보기 옵션