Algorithm JS - 이분 검색

문제

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

입력 설명

첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다. 두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

출력 설명

첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.

알고리즘

• Target 설정(M값)
• N개의 수를 오름차순으로 정렬
• lp , rp(배열의 포인터) 설정 및 배열의 mid 값 지정(Lt + rt / 2)
• While문으로 순회
• 만약, mid값이 M보다 클 경우 rp = mid -1 후 mid 재 설정
• mid값이 M보다 작을 경우 lp = mid + 1 후 mid 재 설정
• target과 같을 때 까지 반복 후 만약 같다면 answer에 midValue + 1 할당
• Answer 출력

소스코드

let input = require("fs").readFileSync(__dirname + "/input.txt").toString().trim().split("\n");

const target = Number(input[0].split(" ")[1]);
const numArr = input[1].split(" ").map((i) => Number(i)).sort((a, b) => a - b);

let answer = 0;
let lp = 0;
let rp = numArr.length - 1;

while (true) {
  let midValue = parseInt((lp + rp) / 2);
  if (numArr[midValue] === target) {
    answer = midValue + 1;
    break;
  } 
  else if (numArr[midValue] > target) rp = midValue - 1;
  else lp = midValue + 1;
}

console.log(answer);