[백준] 온라인 저지 2776번 : 암기왕(Java), 이분 탐색

N(1 ≤ N ≤ 1,000,000), M(1 ≤ M ≤ 1,000,000) 으로, 반복문을 사용해 단순 탐색을 할 경우 시간 복잡도는 O(N * M)이 된다.

여기에 testCase까지 더한다면, 시간 복잡도는 더 증가할 것이다.

 

따라서 이분 탐색이나 Set을 활용해 풀이해야 한다. 이분 탐색의 시간 복잡도는 O(Mlog N)이다.

 

참고 : https://hxxyeoniii.tistory.com/55

이진 탐색(binary search)

 

 

 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int testCase = Integer.parseInt(br.readLine());

		for(int i=0; i<testCase; i++) {
			// 수첩 1
			int N = Integer.parseInt(br.readLine());
			List<Integer> note1 = new ArrayList<>();
            		st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				note1.add(Integer.parseInt(st.nextToken()));
			}

			// 수첩 2
			int M = Integer.parseInt(br.readLine());
			List<Integer> note2 = new ArrayList<>();
            		st = new StringTokenizer(br.readLine());
			for(int k=0; k<M; k++) {
				note2.add(Integer.parseInt(st.nextToken()));
			}

            
           		 Collections.sort(note1);
            
			for(int l=0; l<M; l++) {
                		if(BinarySearch(note1, note2.get(l))) {
					sb.append("1").append("\n");
				} else {
					sb.append("0").append("\n");
				}
			}
		}
        	System.out.println(sb.toString());
	}
    
    private static boolean BinarySearch(List<Integer> list, int target) {
		boolean flag = false;

		int left = 0;
		int right = list.size() - 1;

		while(left <= right) {
			int mid = (left+right) / 2;
            
            		if(list.get(mid) == target) {
                		return true;
            		}
            
			if(list.get(mid) > target) {
				right = mid - 1;
			} else if(list.get(mid) < target) {
				left = mid + 1;
			} 
		}
		return flag;
	}
}