임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.
첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다. 두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.
첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.
입력
8 32
23 87 65 12 57 32 99 81
출력
3
이분탐색 알고리즘은 시간복잡도가 O(log n)인 특징이 있다.
const solution = (target, arr) => {
let answer = 0;
let [left, right] = [0, arr.length - 1];
arr.sort((a, b) => a - b);
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
answer = mid + 1;
break;
} else if (arr[mid] > target) right = mid - 1;
else left = mid + 1;
}
return answer;
};
const tmp = solution(32, [23, 87, 65, 12, 57, 32, 99, 81]);
console.log(tmp); // 3