백준 1920_수 찾기(C++)

 

www.acmicpc.net/problem/1920

1920번: 수 찾기

[문제 풀이]

이분 탐색을 이용하여 풀었습니다.

 

이 문제의 경우 정렬이 되어있지 않으면 완전 탐색을 이용해야 합니다. 하지만 완전 탐색을 이용한다면 시간 초과가 날 것이라 생각하였기 때문에 정렬을 해주고 이분 탐색을 이용하여 문제를 풀어주었습니다.

 

아래 링크를 들어가시면 이분 탐색에 대한 자세한 내용을 정리해 두었습니다. 

 

 

steady-life.tistory.com/57?category=788590

이분 탐색

[코드]

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N, M;

vector<int> A;
vector<int> B;

int main() {

	scanf("%d", &N);

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

		A.push_back(temp);
	}

	scanf("%d", &M);

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

		B.push_back(temp);
	}

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

	for (int i = 0; i < M; i++) {
		
		bool check = false;

		int left = 0;
		int right = N - 1;
		int target = B[i];

		while (left <= right) {

			int mid = (left + right) / 2;

			if (A[mid] > target) {
				right = mid - 1;
			}
			else if (A[mid] < target) {
				left = mid + 1;
			}
			else if (A[mid] == target) {
				check = true;
				break;
			}
		}

		if (check)
			printf("1\n");
		else
			printf("0\n");

	}

	return 0;

}