백준 1920번(수 찾기)[JAVA]

풀이

N이 100,000이 넘어가므로, 반복문(O(n))으로는 시간 초과가 난다. 이진 탐색(O(logn))을 사용하여 풀면 된다.

소스 코드

import java.util.*;

public class Main {
	static int[] nArr;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		nArr = new int[n];
		for (int i = 0; i < n; i++) {
			nArr[i] = sc.nextInt();
		}
		Arrays.sort(nArr);
		
		int m = sc.nextInt();
		for (int i = 0; i < m; i++) {
			int find = sc.nextInt();
			bs(find);
		}
	}
	
	static void bs(int x) {
		int low = 0;
		int high = nArr.length-1;
		boolean flag = false;
		
		while (true) {
			int mid = (high+low)/2;
			if (low > high)
				break;
			
			if (x < nArr[mid]) {
				high = mid-1;
			} else if (x > nArr[mid]) {
				low = mid+1;
			}
			else {
				flag = true;
				break;
			}
		}
		
		if (flag)
			System.out.println(1);
		else
			System.out.println(0);
	}
}

태클 감사합니다.
조언 환영입니다.