Binary Search

1. 이분 검색이란?

  이진 검색은 정렬된 리스트에서 원하는 항목을 찾기에 효율적인 알고리즘이다.  
  이 검색법은 후보 범위가 한 항목으로 좁아질 때까지 찾고자 하는 항목을 포함하고 있는 리스트를 반으로 나누는 과정을 계속 반복한다.

2. 대표문제 1

function binarySearch(arr, target) {
  let answer = 0,
    lt = 0,
    rt = arr.length - 1;
  arr.sort((a, b) => a - b);
  while (lt <= rt) {
    let mid = Math.floor((lt + rt) / 2);
    if (arr[mid] === target) {
      answer = mid;
      break;
    } else if (arr[mid] < target) {
      lt = mid + 1;
    } else {
      rt = mid - 1;
    }
  }
  return answer + 1;
}

 

3.  대표문제 2

function getDvdNums(songs, dvdSize) {
  let cnt = 1,
    sum = 0;
  for (let i = 0; i < songs.length; i++) {
    if (sum + songs[i] > dvdSize) {
      cnt++;
      sum = songs[i];
    } else {
      sum += songs[i];
    }
  }
  return cnt;
}

function solution(songs, dvdNums) {
  let answer;
  let min = Math.max(...songs);
  let max = songs.reduce((acc, cur) => acc + cur);

  while (min <= max) {
    let mid = Math.floor((min + max) / 2);
    if (getDvdNums(songs, mid) <= dvdNums) {
      answer = mid;
      max = mid - 1;
    } else {
      min = mid + 1;
    }
  }
  return answer;
}

 

4. 대표문제 3

function helper(arr, dist) {
  let cnt = 1;
  let ep = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] - ep >= dist) {
      ep = arr[i];
      cnt++;
    }
  }
  return cnt;
}

function solution(arr, num) {
  arr.sort((a, b) => a - b);
  let lt = 1;
  let rt = arr[arr.length - 1];
  let mid;
  let answer;
  while (lt <= rt) {
    mid = Math.floor((lt + rt) / 2);
    if (helper(arr, mid) >= num) {
      answer = mid;
      lt = mid + 1;
    } else {
      rt = mid - 1;
    }
  }
  return answer;
}