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

이분탐색을 이용한 문제였다.

이분탐색을 직접 구현해주어도 좋지만, STL에 있는 binary_search를 이용하여 빠르게 풀어주었다.

실제 코딩테스트에서는 시간이 부족한 경우가 많기 때문에 STL을 활용할 수 있다면 최대한 도움을 받고, 다음 문제를 풀러가는 것이 좋은 것 같다.

 

그리고 이분탐색 하기 전에 데이터 정렬하는 것 잊지 말기

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

int main()
{
	int n, m;
	vector<int> v;

	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		int temp;
		scanf("%d", &temp);
		v.push_back(temp);
	}

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

	scanf("%d", &m);

	for (int i = 0; i < m; i++)
	{
		int target;
		scanf("%d", &target);

		if (binary_search(v.begin(), v.end(), target))
		{
			printf("1\n");
		}
		else
		{
			printf("0\n");
		}
	}
}

 

+추가

 

STL을 사용하지 않고 직접 이분탐색을 구현하는 방법은 다음과 같다.

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

int a[100005];
int n;

int binarysearch(int target)
{
	int st = 0;
	int en = n - 1;
	while (st <= en)
	{
		int mid = (st + en) / 2;
		if (a[mid] < target)
		{
			st = mid + 1;
		}
		else if (a[mid] > target)
		{
			en = mid - 1;
		}
		else
		{
			return 1;
		}
	}
	return 0;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	sort(a, a + n);

	int m;
	cin >> m;
	while (m--)
	{
		int t;
		cin >> t;
		cout << binarysearch(t) << '\n';
	}
}