[C++] 백준 1920: 수 찾기

문제

[C++] 백준 1920: 수 찾기 SILVER 4
https://www.acmicpc.net/problem/1920

 

---

 

접근 방법

이 문제는 주어진 수열에 특정 값이 존재하는지 여부를 빠르게 판단하는 문제이다.
수의 개수가 많기 때문에, 단순히 하나씩 비교하는 선형 탐색은 비효율적이다.

그래서 먼저 수열을 정렬한 뒤, 이진 탐색(Binary Search) 을 이용해 각 값이 존재하는지 확인했다.

이진 탐색은 탐색 범위를 절반씩 줄여 나가기 때문에, 한 번의 탐색을 O(log N)에 수행할 수 있다.

 

구현 시 주의할 점

• 이진 탐색을 사용하려면 반드시 사전에 정렬이 되어 있어야 한다.
• start, end 범위는 start <= end 조건으로 탐색을 진행해야 모든 경우를 포함할 수 있다.
• 값을 찾았을 때는 바로 출력하고 탐색을 종료해야 불필요한 반복을 줄일 수 있다.
• 끝까지 탐색했는데도 찾지 못한 경우에는 0을 출력한다.

 

---

 

코드

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n = 0;
	cin >> n;

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

	sort(vect.begin(), vect.end());

	int find_cnt = 0;
	cin >> find_cnt;
	for (int i = 0; i < find_cnt; i++)
	{
		int find = 0;
		cin >> find;

		int start = 0, end = n - 1;
		bool flag = false;
		while (start <= end)
		{
			int mid = (start + end) / 2;
			int midV = vect[mid];

			if (find == midV)
			{
				flag = true;
				cout << 1 << '\n';
				break;
			}
			else if (find < midV)
				end = mid - 1;
			else if (find > midV)
				start = mid + 1;
		}
		if (flag == false)
			cout << 0 << '\n';
	}

	return 0;
}