[BOJ] 1920 수 찾기

www.acmicpc.net/problem/1920

1920번: 수 찾기

 

학회 스터디 강의할 때 다룬 문제

이분 탐색을 구현해서 푸는 코드와 STL 사용하는 코드 모두 보여드렸다.

int arr[100000];
bool search(int left, int right, int key);
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m;

	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	sort(arr, arr + n);						 // 정렬 필수, <algorithm> 헤더에 포함
	cin >> m;
	while (m--) {
		int query; cin >> query;
		cout << search(0, n, query) << ENDL; // [0, n) 인덱스의 배열에 query 값이 있는지 확인
	}
}

bool search(int left, int right, int key) {
	if (!(left < right)) {			 		 // 탐색할 구간의 크기가 0인 경우
		return false;				 		 // 찾는 값이 없었으므로 false 반환
	}

	int mid = (left + right) / 2;
	if (arr[mid] == key) {			 		 // 찾는 값이 있으면 true 반환
		return true;
	}
	else if (key < arr[mid]) {				 // 중앙값이 key보다 크므로 왼쪽 절반 구간으로 이동
		return search(left, mid, key);
	}
	else if (arr[mid] < key) {				// 중앙값이 key보다 작으므로 오른쪽 절반 구간으로 이동
		return search(mid + 1, right, key);
	}
}

int arr[100000];
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	sort(arr, arr + n);

	int m; cin >> m;
	while (m--) {
		int query; cin >> query;
		cout << binary_search(arr, arr + n, query) << ENDL;	//<algorithm> 헤더
	}
}