[백준 1920 JAVA 자바] 수 찾기

문제는 간단해보이지만

 

1<= N <= 100,000

1<= M <= 100,000

이기 때문에

 

길이가 N인 어레이를 하나하나 조사하다간

100,000 * 100,000번의 연산을 하게됩니다

 

아래 태그에 #이분 탐색 이 있군요

이분 탐색 방식을 이용합시다

 

코드입니다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
		
		int m = Integer.parseInt(br.readLine());
		
		StringTokenizer st2 = new StringTokenizer(br.readLine());
		for (int i=0; i<m; i++) {
			
			sb.append(bina(arr, Integer.parseInt(st2.nextToken())));
			sb.append("\n");
		}
		
		System.out.println(sb);
	}
	
	public static int bina(int[] arr, Integer k) {
		
		Integer a = 0;
		Integer b = arr.length -1;
		
		while(a<=b) {
			Integer mid = (b+a)/2;
			
			if (k<arr[mid]) {				
				b = mid-1;				
			}else if(k>arr[mid]) {			
				a = mid+1;				
			}else {
				return 1;
			}
		}		
		return 0;
	}	
}

이분탐색 하기 전

Arrays.sort(arr)을 통해 정렬을 해줍시다

이분탐색은 크기를 이용하기에 정렬이 필요합니다

 

bina 함수는 이분탐색을 해주는 함수입니다

while문을 보면

mid = (b+a)/2가 있습니다

중간을 기준으로

목표값이 중간보다 큰지 중간보다 작은지 찾아가는겁니다

 

이분 탐색은 전체를 탐색하는 방법보다

최소 2배 이상 빠릅니다 (정렬과정 빼면)