백준 1920 수 찾기

 

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector <long long>a;

void find(int s, int e, long long i) {
	int mid = (s + e) / 2;
	if (e < s) {
		cout << "0\n";
		return;
	}
	if (a[mid] == i) {
		cout << "1\n";
		return;
	}
	if ((e == s||e=s+1 ) && a[e] != i) {
		cout << "0\n";
		return;
	}
	if (a[mid] > i) {
		find(s, mid-1, i);
	}
	if (a[mid] < i) {
		find(mid+1, e, i);
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n;
	for (int i=0; i < n; i++) {
		long long k; 
		cin >> k;
		a.push_back(k);
	}

	cin >> m;
	sort(a.begin(), a.end());
	for (int j = 0; j < m; j++) {
		long long k; 
		cin >> k;
		find(0, a.size()-1, k);
	}
	return 0;
}

배열에 원소를 삽입하고 find 함수를 작성하여 그 안에서 이분탐색을 진행하였다. end>start인 경우에는 정답을 찾지 못한 것이므로 0을 출력, a[mid]가 찾던 값인 경우 1 출력, e==s이거나 e==s+1이면 mid와 s의 값이 같아진다.  그러므로 a[s]가 찾던 값이라면 앞선 경우에서 1이 출력되었을 것이므로 , a[e]가 찾던 값인지 이를 검사해준다. 찾지 못했고 아직 검사할 수 있는 범위가 더 남았다면 이분탐색으로 mid의 값이 찾던 값보다 클 때 end의 범위를 줄이고 찾던 값보다 더 작다면 start의 범위를 키워서 탐색하도록 해주었다.