이분 탐색 알고리즘의 원리는 무엇이고 어떤 문제에서 사용할까?

이분 탐색의 정의

정렬된 배열에서 특정 값을 빠르게 찾아내는 알고리즘입니다.

절반씩 나눠서 탐색하는 특징이 있고, 시간 복잡도는 O(log N) 입니다.

N이 100만개 있을 때 20의 시간 복잡도를 가진다고 합니다.

 

전제 조건

배열이 반드시 정렬 되어있어야 하는데, 오름차순인지 내림차순인지는 상관이 없지만 일반적으로 오름차순을 사용합니다.

 

일반적인 형태 (기본 형태 - JavaScript)

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return true;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return false;
}

 

코드를 보면 arr와 target을 파라미터로 받고 있습니다.

arr는 값을 찾을 배열을 의미하고, target은 배열 안에서 찾아낼 값을 의미합니다.

 

left, right는 각각 현재 시작점과 끝점을 나타내는데,

이분 탐색 알고리즘의 핵심은 이 left와 right를 이동시켜서 배열을 절반으로 처리한다고 보면 될 것 같습니다.

 

mid라는 변수에 left와 right를 더한 값의 절반을 입력해두고, 배열에 mid에 위치한 값이 target보다 작으면 left를 mid + 1로 설정해주고 반대의 경우에는 right를 mid - 1로 설정해주어서 필요한 절반의 배열 부분만 볼 수 있도록 처리합니다.

 

어떤 문제에 적용할 수 있을까?

• 정렬된 배열에서 특정 값을 찾는 문제
  • 백준 1920번
  • 백준 10815번
• 조건을 만족하는 값의 최솟값/최댓값 찾기 (결정문제 + 탐색 범위가 수의 범위)
  • 예산 배정: 이 예산 안에 만족하는 상한선
  • 징검다리 건너기: 최대 몇 칸까지 뛰어넘을 수 있는 지
  • 입국 심사: 모든 사람을 처리하는 데 걸리는 최소 시간
  • 나무 자르기: 이만큼 잘라서 총 M미터가 나오는 최소 높이

 

추천 학습 순서

1. 단순 탐색
2. lower/upper
3. 파라메트릭 서치