백준 1920 수 찾기 C++

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

풀이

이진 탐색 트리(Binary Search Tree)를 이용하여 탐색 범위를 줄여가면서 이 수들이 A 안에 있는지 알아낸다.

이진트리는  각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 

이진 탐색 트리(Binary Search Tree, BST)는 이진 트리의 일종으로, 노드의 왼쪽 가지에는 노드의 값보다 작은 값들만 있고, 오른쪽 가지에는 큰 값들만 있도록 구성되었다. 

 

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

int BinaryTree(int arr[], int n, int k);

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

	int n, m;
	int a[100001];
	int b[100001];
	int check;

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

	sort(a, a + n);

	cin >> m;
	for (int j = 0; j < m; j++) {
		cin >> b[j];
	}

	for (int j = 0; j < m; j++){
		check = BinaryTree(a, n, b[j]);
		cout << check << '\n';
	}
}

int BinaryTree(int arr[], int n, int k) {
	int left = 0;
	int right = n - 1;
	int mid;

	while (left <= right) {
		
		mid = (left + right) / 2;

		if (arr[mid] > k) {
			right = mid - 1;
		}
		else if (arr[mid] < k) {
			left = mid + 1;
		}
		else {
			return 1;
		}
	}

	return 0;
}