백준 1920-수 찾기(cpp)

백준 1920 - 수 찾기

문제

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을 출력한다.

---

문제 설계

이분탐색을 사용하여 숫자가 배열에 존재하는지 알아낸다.

풀이 과정

1. arr[]을 전역변수로 선언하고 값을 받은 후 정렬한다.
2. search 함수에서 찾아야할 값(find)을 인자로 받아 이분탐색을 실행한다.
3. search 함수 설명
   • left와 right가 같을 때까지 반복한다. -> left<right로 하면 find가 정확히 중앙에 있을 때를 계산하지 않는다.
   • mid에 중앙 index값을 준다.
   • 중앙값 arr[mid]와 찾아야하는 값을 비교한다.
   • arr[mid]와 찾아야할 값이 같다면 true 반환
   • 찾아야 할 값이 중간보다 작은 경우 right=mid-1로 만들어 탐색 구간을 반으로 줄인다.
   • 찾아야 할 값이 중간보다 큰 경우 left=mid+1로 만들어 탐색 구간을 반으로 줄인다.
   • left<=right까지 반복했는데 값을 못찾을 경우 false 반환

코드

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

int arr[100001];

bool search(int left, int right, int key)
{
	while(left <= right)
	{
		int mid = (left+right)/2;
		if(arr[mid] == key)  // 값을 찾은 경우 
			return true;
		else if(key < arr[mid])  // 찾아야 하는 값이 중간보다 작은 경우 
			right = mid-1;
		else  // 찾아야 하는 값이 중간보다 큰 경우 
			left = mid+1;
	}
	return false;  // 탐색 실패 
}

int main()
{
	int n, m, find;
	
	scanf("%d", &n);
	for(int i=0; i<n; i++)
	{
		scanf("%d", &arr[i]);
	}
	sort(arr, arr+n);
	
	scanf("%d", &m);
	for(int i=0; i<m; i++)
	{
		scanf("%d", &find);
		if(search(0, n-1, find))
		{
			printf("1\n");
		}
		else printf("0\n"); 
	}
	
	
	return 0;
}

결과

while(left<right)로 해서 틀렸었다.