백준 1920

백준 1920 : 수 찾기

1. 처음에 단순히 C++에서 제공되는 find 함수를 이용해 손쉽게 풀려고 접근했다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, m, a[1000001], target;

int main() {
	cin>>n;
	for(int i=0; i<n; i++) {
		cin>>a[i];
	}
	
	cin>>m;
	for(int i=0; i<m; i++) {
		cin>>target;
		
		if(*find(a, a+n, target)) {
			cout<<1<<"\n";
		} else {
			cout<<0<<"\n";
		}
	}
	
	return 0;
}

그랬더니 시간초과가 났다..

검색해보니 find() 함수가 O(N) 시간이 소요되는 거였다. find 함수를 쓰면 Sequential search를 이용한다고 한다.

따라서 이분탐색을 이용해 다시 풀었다.

정답 코드

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int n, m, a[1000001], target;

//binary search
int bi_search(int L, int R, int arr[], int target) {
	while(L<=R) {
		int mid=(L+R)/2;
	
		if(arr[mid] == target) {
			return 1;
		}
		
		if(arr[mid] > target) {
			R = mid-1;
		}
		else {
			L = mid+1;
		}
	}
			
	return 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin>>n;
	for(int i=0; i<n; i++) {
		cin>>a[i];
	}
	
	sort(a, a+n);
	
	
	cin>>m;
	for(int i=0; i<m; i++) {
		cin>>target;		
		int ans = bi_search(0, n-1, a, target);
		
		cout<<ans<<"\n";
	}
	
	
	return 0;
}