[210504][백준/BOJ] 1920번 수 찾기

문제

입출력

풀이

A 배열을 오름차순으로 정렬하고 m개의 개수를 입력받으면서 이 값들이 A 배열에 존재하는지 확인하는 문제이다. Binary Search를 이용해서 문제를 풀 수 있다.

left, right, mid 값을 정한 다음에 mid 값이 찾는 값보다 작다면 right을 mid - 1로 이동하고 mid 값이 찾는 값보다 크다면 left를 mid + 1로 이동한다.

코드

#include <bits/stdc++.h>
using namespace std;

int a[100002];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m, num;

	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 >> num;

		int left = 0;
		int right = n - 1;
		int mid;
		bool flag = true;

		while (right - left >= 0)
		{
			mid = (left + right) / 2;

			if (a[mid] == num) // 일치
			{
				flag = false;
				break;
			}
			else if (a[mid] > num) // 찾는 값보다 중앙값이 작으면 
				right = mid - 1;
			else // 찾는 값보다 중앙값이 크면
				left = mid + 1;
		}

		if (flag == false) cout << 1 << '\n';
		else cout << 0 << '\n';
	}
}