[백준 1920] 수 찾기

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

소스코드

public class Q1920 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int numCnt;
		int[] arr;
		int searchCnt;
		int search;
		
		numCnt = Integer.parseInt(br.readLine());
		arr = new int[numCnt];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<numCnt; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		// 이분탐색을 위한 정렬 (이분탐색은 정렬된 상태에서만 사용할 수 있다)
		Arrays.sort(arr);
		
		searchCnt = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<searchCnt; i++) {
			search = Integer.parseInt(st.nextToken());
			if(binarySearch(arr, search)) {
				System.out.println("1");
			}else {
				System.out.println("0");
			}
		}
	}
	
	public static boolean binarySearch(int[] arr, int num) {
		int low = 0;
		int high = arr.length-1;
		int mid = 0;
		
		while(low<=high) {
			mid = (low+high)/2;
			if(arr[mid]==num) {
				return true;
			}else if(arr[mid]>num) {
				high = mid-1;
			}else {
				low = mid+1;
			}
		}
		return false;
	}
}

---

이전에 한번 올렸었습니다 ( https://skwzz.tistory.com/11 )
재귀적으로 이분탐색을 하셔도 무방합니당..
그리고 저는 단계별 문제를 통해서 문제를 풀었기 때문에 이분탐색이라는걸 알고 들어와서 풀었지만
모르고 푼다면 아마 제 생각엔 타임오버가 뜨지 않을까요? 그래서 정답비율도 27% 인거 같고...
제 기억으로는 아마 1억번의 루프가 대충 1초로 기억하는데용, 입력조건을 보면 처음 배열의 크기가 최대 10만,
검사할 숫자의 최대 갯수도 10만개이므로 최악의 경우 십억개의 검사를 해야합니다. 그리고 시간 제한은 2초니까 나가리가 되겟죵?