[Algorithm] 이분 탐색 (Binary Search)

이분 탐색은 결정 문제(Decision Problem)의 답이 이분적일 때 사용할 수 있는 탐색 기법이다.

 

 

❗️ 결정 문제란?
답이 Yes or No인 문제를 의미하며, 보통 1개의 parameter를 가진다.

 

 

1 ~ 50까지 오름차순 정렬된 카드 더미에서 28번 카드를 찾는 문제가 있을 때, 첫 번째 카드부터 i번째 카드는 v[i], 28은 val로 설정한다.
이 경우 결정 문제를 "v[i] >= val인가?"로 잡으면, 결정 문제의 답은 i가 증가함에 따라 F, F, ..., F, T, T, ..., T와 같이 분포한다.

이 때 찾고자 하는 값은 처음으로 v[i] >= val인 지점, 즉 처음 결정 문제가 True가 되는 i값이 된다.

 

⭐️ 구현 방법

이분 탐색의 구현은

1) Check(lo) != Check(hi)가 되도록 lo, hi의 초기값을 설정한 뒤,
2) lo + 1 < hi인 동안 mid = (lo + hi) / 2를 구해서,
3) Check(lo) == Check(mid)라면 lo = mid를, Check(hi) == Check(mid)라면 hi = mid로 설정한다.

 

이분 탐색이 끝나면 lo, hi는 결정 문제의 답이 바뀌는 경계에 위치하게 되며,

만약 결정 문제의 답의 분포가 F ~ T인데 정답이 가장 큰 F라면 lo를, 가장 작은 T라면 hi를 출력한다.

 

1. 경계를 포함하도록, 즉 Check(lo) != Check(hi)가 되도록 [lo, hi]를 설정한다.

2. Check(lo) == Check(mid)라면 lo = mid, 아니라면 hi = mid를 반복한다.

 

3. lo + 1 == hi가 되면 loop 종료, lo와 hi는 경계에 위치한다.

 

 

 

⭐️  문제 예시: bj2805 나무 자르기

결정 문제를 "mid 높이에 절단기를 위치했을 때, m 이상의 나무를 얻을 수 있는가?"로 잡으면,

Check(mid)의 분포가 T, ..., T, F, ..., F이고, 구하는 답은 Check(mid) = True인 mid의 최댓값이다.

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

const [N, M] = input[0].split(" ").map(Number);
const trees = input[1].split(" ").map(Number);

function solution() {
  let left = 0,
    right = 1000000000,
    mid = 0;

  while (left + 1 < right) {
    mid = Math.floor((left + right) / 2);
    // M보다 많다 -> 많이 잘라간다 -> 높이를 높게 설정한다 -> left값을 조정한다.
    if (!Check(mid)) left = mid;
    else right = mid;
  }
  console.log(left);
}

function Check(mid) {
  let sum = 0;
  for (let i = 0; i < trees.length; i++) {
    if (trees[i] > mid) sum += trees[i] - mid;
    if (sum >= M) return false;
  }
  return true;
}
solution();

 

❗️결정 문제의 답은 항상 F~T의 분포가 아니라, T~F의 분포일 수도 있다.
또한 정답은 경계의 왼쪽일 수도 있고, 오른쪽일 수도 있으므로 문제별로 잘 생각해야 한다.

---

⭐️  lower_bound, upper_bound

lower_bound는 v[i-1] < k <= v[i]인 i를 찾으며, v[i] >= k인 i의 최솟값을 반환한다.
upper_bound는 v[i-1] <= k < v[i]인 i를 찾으며, v[i] > k인 i의 최솟값을 반환한다.

const lower_bound = (v, x) => {
    const n = v.length;
    let lo = -1, hi = n;
    while (lo + 1 < hi) {
        let mid = Math.floor((lo + hi)/2);
        if (!(v[mid] >= x)) lo = mid;
        else hi = mid;
    }
    return hi;
}

const upper_bound = (v, x) => {
    const n = v.length;
    let lo = -1, hi = n;
    while (lo + 1 < hi) {
        let mid = Math.floor((lo + hi)/2);
        if (!(v[mid] > x)) lo = mid;
        else hi = mid;
    }
    return hi;
}

console.log(lower_bound([1, 2, 3, 3, 4], 3)); // 2
console.log(upper_bound([1, 2, 3, 3, 4], 3)); // 4

⭐️  자주 하는 실수

1. lo, hi는 항상 정답의 범위를 나타낼 수 있어야 한다. 예를 들어 lo를 출력해야 하는 문제의 답이 최대 n일 때, hi = n으로 선언하거나, hi를 출력해야 하는 문제의 답이 최소 0일 때 lo = 0으로 선언하면 안된다. (hi = n + 1, lo = -1로 선언해야 한다.)

2. 오버플로우에 주의한다.

3. 결정 문제의 정의에 맞게 Check 함수를 잘 구현해야 한다. Check 함수의 부등호를 조금만 틀려도 전혀 다른 값이 나올 수 있다.

---

 

Reference

• 이분 탐색(Binary Search) 헷갈리지 않게 구현하기