[인프런] Node.js / 섹션7-정렬과 그리디, 결정알고리즘 / 10. 이분검색

문제

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.

 

풀이

function solution(target, arr) {
  let min = 0;
  let max = arr.length - 1;
  let median;

  arr.sort((a, b) => a - b);
  while (min <= max) {
    median = Math.floor((min + max) / 2);
    if (target > arr[median]) {
      min = median + 1;
    } else if (target < arr[median]) {
      max = median - 1;
    } else if (target === arr[median]) {
      return median + 1;
    } else {
      return "없는 값";
    }
  }
}

let arr = [23, 87, 65, 12, 57, 32, 99, 81];
console.log(solution(32, arr));

먼저 오름차순으로 정렬해주고, 리스트의 중간값을 찾아 원하는 값과 비교해서 진행한다.

중간값 = (최솟값 + 최댓값) /2

중간값 위치에 해당하는 값과 찾고자하는 값과 비교 한다. 만약 찾고자하는 값이 중간값보다 크다면 중간값 이하는 검색할 필요가 없고 작다면 중간값 이상의 값은 검색할 필요가 없다. 이렇게 원하는 값 찾을 때까지 반씩 쪼개며 찾는다.