1. Problem 📃

[ 수 찾기 ]

https://www.acmicpc.net/problem/1920

[ 문제 ]

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

2. Input 📇

[ 입력 ]

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

3. Output 📠

[ 출력 ]

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

4. Example 📚

[ 입출력 예시 ]

5. Solution 🔑

1. 정수의 개수를 받아줄 변수(N)를 선언하여 값을 받아준다.
   그 후 정수 값들을 N개의 개수 만큼 받아줄 배열 변수(A)를 선언하여, 값들을 배열에 모두 담고, Arrays.sort(A)를 이용하여 A배열을 정렬해준다.
   
   
2. A배열과 몇 개의 값을 비교할지 정수의 개수를 담을 변수(M)를 선언하여 값을 받는다.
   그 후, 들어올 값들을 하나씩 비교하는데 이때 메서드를 불러와서 비교한다.
   
   
3. 이분탐색을 이용한 메서드를 작성해준다.
   메서드의 매개변수는 배열 A(arr)와 내가 비교할 입력 받은 값(val)을 받아준다.
   가장 높은 인덱스를 arr의 길이에서 -1 뺀 값, 즉 마지막을 high라는 변수에 담아주고
   가장 작은 인덱스 0을 low라는 변수에 담아 시작한다.
   
   
4. 무한루프를 돌려 low값이 high값보다 같거나 작으면 계속 돌린다.
   중간값(mid)는 (low + high)/2 를 하여 mid값을 구한다.
   배열 arr[mid]값이 내가 찾는 값보다 뒤에 있다면 low값을 중간값(mid)에 +1 한 값으로, 배열 arr[mid]값이 내가 찾는 값보다 앞에 있다면 high값을 중간값(mid)에 -1 한 값으로, 바꿔주면서 while문을 빠져 나올 동안 반복한다.
   만약, 내가 찾는 값이 배열 arr[mid]과 같다면 해당 값을 반환하고, 해당 값이 없다면 -1을 반환해주었다.
   
   
5. 반환 받은 값으로 메인함수에서 -1을 반환 받았다면, 해당 값은 배열에 존재하지 않는 값이 되므로 0을 출력하고, 그 외 값을 반환 받았다면 해당 값은 배열에 존재하는 값이 되므로 1을 출력하여준다. 이를 M만큼 반복한다.

6. Code 💻

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	
	public static int binarySearch(int[] arr, int val) {
		
		int high = arr.length-1;
		int low = 0;
		while(low <= high) {
			
			int mid = (low + high) / 2;
			
			if(val > arr[mid]) {
				low = mid + 1;
			}
			else if(val < arr[mid]) {
				high = mid - 1;
			}
			else {
				return mid;
			}
		}
		
		return -1;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int[] A = new int[N];
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(A);
		
		st = new StringTokenizer(br.readLine(), " ");
		
		int M = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<M; i++) {
			if(binarySearch(A, Integer.parseInt(st.nextToken())) != -1) {
				System.out.println(1);
			}
			else {
				System.out.println(0);
			}
		}
		
	}

}