백준 1920 수 찾기 풀이

문제

https://www.acmicpc.net/problem/1920

&Title
1920번 - 수 찾기

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


&Input
첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 
정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 
주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 
존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다. 


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

&Example
-input
5
4 1 5 2 3
5
1 3 7 9 5

-output
1
1
0
0
1

요약

• 해당 배열에 주어진 숫자가 있는지 확인하여 존재하면 1, 존재하지 않으면 0을 출력하라

접근

• 이진탐색을 사용한다.

풀이

1. 이진탐색은 log2(N)으로 원하는 값이 있는지 없는지 찾을 수 있다. 이때 데이터가 정렬되어 있어야한다.
2. 먼저 데이터를 정렬해준다.
3. 시작점과 끝점을 이용해 중간값이 타겟보다 큰가 작은가에 따라 시작점, 끝점을 갱신해준다.
4. st <= en 인 이유는 st == en 인 경우가 타겟일수도 있기 때문이다.

소스

#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
int arr[100000];

int BinarySearch(int tg) {
	int st = 0, en = n - 1;
	while (st <= en) {
		int mid = (st + en) / 2;
		if (arr[mid] < tg)
			st = mid + 1;
		else if (arr[mid] > tg)
			en = mid - 1;
		else
			return 1;
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> arr[i];
	sort(&arr[0], &arr[n]);
	cin >> m;
	int t;
	for (int i = 0; i < m; ++i) {
		cin >> t;
		cout << BinarySearch(t) << '\n';
	}
	return 0;
}