1920번: 수 찾기 [C++]

문제

 

 

풀이

선형탐색(Linear Search)을 이용하면 시간초과가 발생하기 때문에 이분탐색(Binary Search)을 통해 해결하였습니다.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100001];

void binary_search(int list[], int key, int right) {
	int left = 0;
	int middle;

	while (left <= right) {
		middle = (left + right) / 2;

		if (key == list[middle]) {
			cout << "1\n";
			return;
			}
		else if (key > list[middle])
			left = middle + 1;
		else if (key < list[middle])
			right = middle - 1;
	}

	cout << "0\n";
	return;
}

int main() {
	int n, m, num;

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i];
		
	sort(arr, arr + n);

	cin >> m;

	for (int i = 0; i < m; i++) {
		cin >> num;

		binary_search(arr, num, n - 1);
	}

	return 0;
}