이분 탐색 / 이진탐색 (Binary Search)

*️⃣ 개념

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
• 배열 내부의 데이터가 오름차순 또는 내림차순으로 정렬되어 있어야만 사용할 수 있는 알고리즘이다.

 

*️⃣ 탐색 과정

• 변수 3개(low, high, mid)를 사용하여 탐색한다. 
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.

 

 

*️⃣ 응용 문제 풀이

백준 1654  https://www.acmicpc.net/problem/1654

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

function solution(arr) {
  const [K, N] = arr.shift().split(' ').map(Number);
  const lan = arr.map(row => row).sort();
  
  // 이진 탐색 초기 설정: 랜선 길이의 최소값과 최대값
  let low = 1;
  let high = Math.max(...lan);
  let answer = 0;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    let cnt = 0;

    for (let i = 0; i < K; i++) {
      cnt += Math.floor(lan[i] / mid);
    }
    
    if (cnt >= N) { // 자른 랜선 개수가 N 이상이면, 더 긴 길이 시도
      answer = mid;  
      low = mid + 1;  
    } else { // 자른 랜선 개수가 N보다 작다면 길이를 줄임
      high = mid - 1;  
    }
  }

  return answer;
}

console.log(solution(input));