시간제한 2초, 백준 1920번

• 문제 분석

N (1 ≤ N ≤ 100000)이므로 단순 반복문으로는 이 문제를 해결할 수 없다.

→ 이진 탐색을 적용하면 O(nlogn)의 시간 복잡도로 문제를 해결할 수 있다.

package practice29;

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

public class Practice29 {//백준 1920번

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[]A = new int[N];
		for(int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}
		Arrays.sort(A);
		int M = sc.nextInt();
		for(int i = 0; i < M; i++) {
			boolean find = false;
			int target = sc.nextInt();
			
			int start = 0;
			int end = A.length - 1;
			while(start <= end) {
				int midIndex = (start + end) / 2;
				int midValue = A[midIndex];
				
				if(midValue > target) {
					end = midIndex - 1;
				}else if(midValue < target) {
					start = midIndex + 1;
				}else {
					find = true;
					break;
				}
			}
			
			if(find) {
				System.out.println("1");
			}else {
				System.out.println("0");
			}
		}
		sc.close();
		
	}

}