JavaScript 코딩테스트 - 이분탐색 (binary_search)

코딩 테스트 대비 저장용 포스트입니다.

C++에는 algorithm 으로 해당 기능을 지원했는데 없어서 구현해보았다.

BOJ 1822번: 차집합 문제

"use strcit";

const binarySearch = (arr, target) => {
  let le = 0,
    ri = arr.length;
  while (le < ri) {
    const mid = Math.floor((le + ri) / 2);
    if (target === arr[mid]) {
      return mid;
    } else if (target < arr[mid]) {
      ri = mid;
    } else {
      le = mid + 1;
    }
  }
  return -1;
};

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
const arrA = input[1]
  .split(" ")
  .map(Number)
  .sort((a, b) => a - b);
const arrB = input[2]
  .split(" ")
  .map(Number)
  .sort((a, b) => a - b);
const answer = arrA.filter((target) => binarySearch(arrB, target) === -1);

console.log(answer.length);
if (answer.length) {
  console.log(answer.join(" "));
}