[백준] 1920번 수 찾기

문제 링크

 

풀이

이분 탐색 혹은 이진 탐색은 매 탐색 마다 탐색 범위를 절반으로 줄여 나가는 방식입니다. O(logN)의 시간 복잡도를 가지는데요. 약 40억 개의 데이터라도 32번 이하의 횟수에서 원하는 데이터를 찾을 수 있습니다. 찾을 수 없더라도 32번만에 알 수 있는 것이지요. 코드에서 find가 A[mid]가 되거나 혹은 mid == low == high 상황일 때(이 경우는 최대로 다 순회한 상태) 값을 찾았다고 판정하게 됩니다. 그리고 이분 탐색은 반드시 데이터가 정렬되어 있어야 합니다. 중간 값을 기준으로 요소의 크고 작음을 이용하는 것이기 때문입니다.

 

기본 흐름은 찾고자 하는 주어진 정수 데이터의 중간 값을 구해서 중간 값이 찾고자 하는 데이터보다 작으면 low 인덱스를 mid + 1로 갱신해주고, 찾고자 하는 데이터가 중간 값보다 작으면 high 인덱스는 mid -1로 갱신해주는 것을 반복하는 것입니다. 최대한 순회하게 되면 mid, high, low가 전부 같아지고요, 그 전에 찾게 되면 mid번째 인덱스의 요소가 우리가 찾고자 하는 데이터가 됩니다. 이 두 경우가 아니라면 찾고자 하는 데이터가 없는 것입니다.

 

코드

#include <cstdio>
#include <algorithm>
int A[100000];
int N;
int binary_search(int find)
{
	int low = 0, high = N - 1;
	while (low <= high)
	{
		int mid = (low + high) / 2;
		if (find < A[mid])
			high = mid - 1;
		else if (find > A[mid])
			low = mid + 1;
		else
			return 1;
	}
	return 0;
}
int main()
{
	int find[100000] = {};
	int M;
	scanf("%d", &N);
	for (int i = 0; i < N; ++i)
		scanf("%d", &A[i]);
	std::sort(&A[0], &A[N]);
	scanf("%d", &M);
	for (int i = 0; i < M; ++i)
		scanf("%d", &find[i]);
	for (int i = 0; i < M; ++i)
		printf("%d\n", binary_search(find[i]));
}