[ JAVA / 백준 : 1920 ] 수 찾기

조건

M개의 숫자를 입력받아, 앞에 입력받았던 N개에 숫자에 존재하면 1, 없으면 0 출력

 풀이

2초안에 풀어야하니까 O(log n)인 이진탐색으로 풀었다

 

---

import java.util.Arrays;
import java.util.Scanner;

public class 수찾기 {

	public static boolean binarySearch(int[] array, int target, int start, int end) {
		while(start <= end) {			
			int middle = (start + end) / 2 ;
			
			if(target == array[middle]) {
				return true;
			} else if(array[middle] > target){
				end = middle - 1;
			} else {
				start = middle + 1;
			}
		}
		
		return false;
	}
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int N;
		N = scan.nextInt();
		int[] array = new int[N];
		
		for(int i = 0; i < N; i++) {
			array[i] = scan.nextInt();
		}
		Arrays.sort(array);
		int M = scan.nextInt();
		for(int i = 0; i < M; i++) {
			int t = scan.nextInt();
			if(binarySearch(array, t, 0, N - 1))
				System.out.println(1);
			else
				System.out.println(0);
		}
		scan.close();
	}
}