[c++] 백준 1920 수 찾기

백준 단계별로 풀어보기 [이분 탐색] 수 찾기

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

1920번: 수 찾기

 

[풀이]

이진 탐색으로 find 배열의 수가 arr 배열에 존재하는지 검색하고, 존재하면 1을 존재하지 않으면 0을 출력한다.

 

[코드]

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

int arr[100001];
int find[100001];

int binary_search(int as, int ae, int key) {
	if (as > ae) {
		std::cout << "0\n";
		return 0;
	}
	int am = (as + ae) / 2;
	if (arr[am] == key) {
		std::cout << "1\n";
		return am;
	}
	else if (arr[am] < key) {
		return binary_search(am + 1, ae, key);
	}
	else {
		return binary_search(0, am - 1, key);
	}
}

int main() {
	//이분 탐색
	int n;
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		std::cin >> arr[i];
	}
	int m;
	std::cin >> m;
	for (int i = 0; i < m; i++) {
		std::cin >> find[i];
	}

	std::sort(arr, arr + n);

	//arr에 find 수가 존재하면 1, 없으면 0 출력.
	for (int i = 0; i < m; i++) {
		binary_search(0, n - 1, find[i]);
	}
}