백준 1920 수 찾기

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 배열을 입력받고 그 배열에 숫자가 존재하는지 찾아서 1 / 0 을 출력하는 문제입니다. 배열의 크기와 찾을 수 의 크기가 100000까지 가능하므로 하나씩 배열을 탐색하며 찾는 방법은 시간초과가 날 것입니다. 따라서 이분탐색을 이용하는 문제입니다.

 

이분탐색을 하기 위해서 입력받은 배열을 정렬하고 중간값을 기준으로 찾는 값과 비교하여 오른쪽 왼쪽으로 이동한 뒤 다시 중간값을 기준으로 찾으며 logN의 시간으로 탐색을 할 수 있는 방법입니다.

 

다음은 코드입니다.

 

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

int N,M;

int bsearch(int x, int*arr, int start, int end) {
	int mid = (start+end)/2;
	
	if(start > end)
		return 0;
	if(arr[mid] == x)
		return 1;
	else if(arr[mid] > x) 
		bsearch(x, arr, start, mid-1);
	else if(arr[mid] < x) 
		bsearch(x, arr, mid+1, end);
	
	
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N,M;
	cin >> N;
	int arr[N];
	for(int i = 0; i < N; i++)
		cin >> arr[i];
	
	sort(arr, arr+N);
	cin >> M; 
	
	for(int i = 0; i < M; i++) {
		int x;
		cin >> x;
		cout<<bsearch(x, arr, 0, N-1)<<'\n';
	}
	return 0;
}