[백준] 1920번 수 찾기

문제

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을 출력한다.

 

#include <bits/stdc++.h>
using namespace std;  
int result[500001];
int main(){
  int n;
  cin >> n;
  int input[n];
  for(int i = 0;i <n;i++) {
    cin >> input[i];
  }
  sort(input,input+n);

  int m;
  cin >> m;
  for (int i = 0; i< m;i++) {
    int find;
    cin >> find;
    int left = 0; int right = n;
    while (left <= right) {
      int mid = (left + right)/2;
      if (input[mid] > find) {
        right = mid -1;
      } else if (input[mid] < find) {
        left = mid + 1;
      } else {
        result[i] = 1;
        break;
      }
    }
  }
 for (int i = 0; i<m;i++) {
   cout << result[i] <<  "\n";
 }

} 

이분 탐색으로 풀어야 되는 문제입니다. 이분 탐색의 가장 큰 특징은 정렬을 미리 해둬야한 다는 점이랍니다.

#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, arr[100005] = {}, m;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }
    cin >> m;
    sort(arr, arr + n);
    for(int i=0;i<m;i++){
        int k; cin >> k;
        int lo = 0, hi = n - 1, flag = 0;
        while(lo <= hi){
            int mid = (lo + hi) / 2;
            if(k == arr[mid]){
                cout << 1 << '\n';
                flag = 1;
                break;
            }
            else if(k > arr[mid]) lo = mid + 1;
            else hi = mid - 1;
        }
        if(flag == 0){
            cout << 0 << '\n';
        }
    }
}

크게 달라지지 않는 것 같다.