[알고리즘] 이분탐색

알고리즘 공부를 시작했다. 수포자에게 수학은 어렵다.

그래도 해야지 ...

 

 

 

오늘은 이분탐색에 대해 정리하고자 한다.

---

1. 이분 탐색이란?

이분탐색이란, 정렬된 배열에서 어떤 값을 빠르게 찾기 위한 알고리즘이다.

 

답을 찾아가는 여정은 길지 않다.

• 배열의 가운데 값을 확인
• 내가 찾는 값과 비교
• 더 작은 쪽 or 더 큰 쪽으로 절반을 버리고 다시 탐색!

 

이렇게 하면 매번 탐색 범위가 반으로 줄어들기 때문에 시간 복잡도는 O(log N) 즉, 매우 빠르다.

 

 

---

2. 왜 정렬되어 있어야 하는가?

정렬이 안 되어 있으면, 어느 방향으로 더 가야하는지 판단할 수 없기 때문이다.

const arr = [1, 3, 2, 6, 4]
arr.sort();
console.log(arr); // [ 1, 2, 3, 4, 6 ]

항상 이분 탐색을 쓰기 전에 정렬 여부를 확인하여 sort method를 사용하여 정렬해야 한다.

 

---

3. 이분 탐색의 기본 코드

Python, Java 등 다양한 프로그래밍 언어에서는 이분 탐색을 기본으로 제공한다.

JavaScript는 제공해주지 않으므로 직접 구현해야한다.

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

  while (left <= right) {
    let mid = ((left + right) / 2) | 0;

    if (arr[mid] === target) {
      return mid;  // 찾음!
    } else if (arr[mid] < target) {
      left = mid + 1;  // 오른쪽으로 탐색
    } else {
      right = mid - 1;  // 왼쪽으로 탐색
    }
  }

  return -1;  // 못 찾음
}

 

---

4. 과정 이해하기

배열과 target이 있다.

target과 값이 같은 배열의 인덱스를 찾아야 한다.

arr = [1, 3, 5, 7, 9, 11, 13]
target = 9

왼쪽 인덱스는 0, 오른쪽 인덱스는 6, 중간 인덱스는 3이다.

중간 인덱스의 값은 7이고, 이는 target 값인 9보다 작다.

 

오른쪽 탐색을 진행한다.

왼쪽 인덱스는 4, 오른쪽 인덱스는 6, 중간 인덱스는 5이다.

중간 인덱스의 값은 11이고, 이는 target 값인 9보다 크다.

 

왼쪽 탐색을 진행한다.

왼쪽 인덱스는 4, 오른쪽 인덱스도 4이다. 인덱스가 같으므로 탐색 종료 직전이 된다.

중간 인덱스는 (4 + 4) / 2 이므로 4이다.
중간 인덱스의 값은 9이고 target 값과 같으로 인덱스는 4이다.

 

---

5. 응용하기

이분 탐색은 단순히 값을 찾는 것 외에도

• 가장 작은 값
• 가장 큰 값
• 조건을 만족하는 최소/최대값

찾을 때에도 사용 가능하다.

이것을 Parametric Search라고 한다.

 

N개의 나무가 있고, 톱날을 H 높이로 설정했을 때 얻을 수 있는 나무 길이의 총합이 M 이상이 되게 하려고 해.
H의 최댓값은 얼마일까? (문제 출처: 백준)

 

이 문제는 특정 H값을 정해서 조건을 만족하는지 확인해야 한다.

이럴 때 이분 탐색으로 정답 범위를 좁혀가며 탐색한다.

const getMaxSawHeight = (trees, M) => {
  let left = 0;
  let right = Math.max(...trees);
  let result = 0;

  while (left <= right) {
      const mid = ((left + right) / 2) | 0;

    // 잘린 나무의 총 길이 계산
    const total = trees.reduce((sum, tree) => {
      if (tree > mid) {
        return sum + (tree - mid);
      }

       return sum;
    }, 0);

    if (total >= M) {
      // 조건을 만족하므로, 더 높게 잘라도 되는지 본다
      result = mid;
      left = mid + 1;
    } else {
      // 너무 많이 잘라서 부족 → 더 낮게 잘라야 함
      right = mid - 1;
    }
  }

  return result;
}

// 예시 실행
const trees = [20, 15, 10, 17];
const M = 7;

console.log(getMaxSawHeight(trees, M));  // 출력: 15

 

파라메트릭 서치는 좀 더 이해하고 자주 봐야할 거 같다....