문제 출처

1. 문제설명

  • N개의 정수 A[1], A[2], …, A[N]이 주어진다.
  • 이 안에 X라는 정수가 존재하는지?



2. 알고리즘 설계

  • Binary search 문제이다.



3. 로직

  • 이진탐색은 기본적으로 숫자가 정렬되어 있어야 한다.
  • 처음엔 배열의 중간 위치에서 탐색을 시작한다.
  • 중간 위치의 값이 타겟보다 작다면, left = mid+1
  • 중간 위치의 값이 타겟보다 크다면, right = mid - 1



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int arr[100000];
int N, M;

int binary_search(int n) 
{
    int left = 0, right = N - 1;
    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == n) return 1;
        else if (arr[mid] < n) left = mid + 1;
        else right = mid - 1;
    }
    return 0;
}

int main() 
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + N);
	cin >> M;
	for (int target, i = 0; i < M; i++) {
		cin >> target;
		cout << binary_search(target) << "\n";
	}
}