백준 1920번 c++ 풀이

안녕하세요 오늘은 이분 탐색을 이용한 문제를 풀어보겠습니다.

 

이 문제는 쉽지만 이분탐색을 이용하여 풀어야한다는 점이 약간 까다롭다고 할 수 있겠습니다.

바이너리 서치를 구현한 함수를 잘 보면서 이해하시길 바랍니다.

 

코드:

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int binarySearch(int low, int high, int target){
	if (low > high) return 0;
	else{
        int mid = (low + high) / 2;
        if (v[mid] == target) return 1;
        else if (v[mid] > target) return binarySearch(low, mid - 1, target);
		else return binarySearch(mid + 1, high, target);
    }
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N;
	cin>>N;
	for(int i = 0; i<N; i++){
		int x;
		cin>>x;
		v.emplace_back(x);
	}
	sort(v.begin(), v.end());
	int M;
	cin>>M;
	for(int i = 0; i<M; i++){
		int x;
		cin>>x;
		cout<<binarySearch(0, N-1, x)<<"\n";
	}
}