수 찾기

문제설명

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 > 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

문제풀이

1. 이분 탐색을 이용한다.
2. 수열 배열을 정렬.
3. left=0 right=수열의 길이로 둔다.
4. left <= right까지 while문을 돌리는데, mid를 구해주고 suArr[mid]보다 target 숫자를 비교
   1. 작으면 => right를 mid-1만큼 당겨줌.
   2. 크면 => left를 미드 mid+1만큼 당겨줌.
   3. 같으면 1을 찍고 return;
5. while문을 다 돌았다는 것은 찾는 숫자가 없는 것이므로 0을 찍음.

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
// const input = fs.readFileSync("./stdin").toString().trim().split("\n");

const su = +input[0];
const suArr = input[1].split(" ").map(e => +e);
const targetArr = input[3].split(" ").map(e => +e);

suArr.sort((a, b) => a - b);

let result = [];
targetArr.forEach(target => {
  let left = 0;
  let right = su - 1;
  while (left <= right) {
    let mid = parseInt((left + right) / 2);
    if (target < suArr[mid]) {
      right = mid - 1;
    } else if (target > suArr[mid]) {
      left = mid + 1;
    } else {
      console.log(1);
      return;
    }
  }
  console.log(0);
});