[JS] 이진탐색 (Binary Search)

❗️이진탐색 (Binary Search)

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 탐색하는 방법
• 순차탐색 $O(N)$ > 이진탐색 $O(logN)$ : 이진탐색이 더 빠르게 처리

✅ 구현방식

arr : 탐색하고자하는 정렬된 리스트
left,right,mid : 탐색하는 인덱스
target : 찾고자 하는 값
while (left <= right) 일때 mid값을 지정하고 루프
if (arr[mid] < target) left = mid + 1;
if (arr[mid] > target) right = mid - 1;
if (arr[mid] === target) return mid;

❗️ 수 찾기 - 백준 1920번

let dir = __dirname + "/1920.txt";
const path = process.platform === "linux" ? "./dev/stdin" : dir;
const input = require("fs").readFileSync(path).toString().trim().split("\n");

let N = Number(input.shift());
let arr = input.shift().split(" ").map(Number);
// binary search를 하기전에 리스트는 항상 정렬되어 있어야함
arr = arr.sort((a, b) => a - b);
let M = Number(input.shift());
let targets = input.shift().split(" ").map(Number);

targets.forEach((target) => {
  console.log(binary(arr, target));
});

function binary(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return 1;
    } else if (arr[mid] > target) {
      right = mid - 1;
    } else if (arr[mid] < target) {
      left = mid + 1;
    }
  }
  return 0;
}