이분검색 (이분 탐색)

문제

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

제한사항

입출력 예

풀이

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

  return answer;
}

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

시작과 끝을 각각 변수에 저장해두고, 중앙 지점을 찾는다. 중앙 지점과 target을 비교했을 때 target이 시작점을 높혀 중앙을 높히고 target이 작다면 끝지점을 낮춰서 중앙을 낮추는 방식으로 탐색해나간다.

매 사이클에 요소가 반씩 줄어들어 효율적인 알고리즘이다. 후에 기술될 결정 알고리즘에 사용된다.