[BOJ 1920번] 수 찾기(JAVA)

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

1920번: 수 찾기

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

class Main{
	
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	
	public static void main(String args[]) throws Exception {
	   int N=Integer.parseInt(br.readLine());
	   int arr1[]=new int[N];
	   String s[]=br.readLine().split(" ");
	   for(int i=0;i<N;i++) {
		   arr1[i]=Integer.parseInt(s[i]);
	   }
	   int M=Integer.parseInt(br.readLine());
	   int arr2[]=new int[M];
	   String s2[]=br.readLine().split(" ");
	   for(int i=0;i<M;i++) {
		   arr2[i]=Integer.parseInt(s2[i]);
	   }
	   Arrays.sort(arr1);
	   for(int i=0;i<M;i++) {
		   int left=0, right=N-1;
		   int result=0;
		   while(left<=right) {
			   int mid=(left+right)/2;
			   if(arr2[i]>arr1[mid]) left=mid+1;
			   else if(arr2[i]<arr1[mid]) right=mid-1;
			   else {
				   result=1;
				   break;
			   }
		   }
		   sb.append(result+"\n");
	   }
	   System.out.println(sb);
	}
}

이분탐색은, 탐색하는 구간을 절반으로 나누는 것을 반복하며 값을 찾는 기법입니다.

만약 중간값 < 찾는 값 이면 중간 값보다 큰 쪽의 구간을 다시 절반으로 나누고, 

중간값 > 찾는 값 이면 중간 값보다 작은 쪽의 구간을 절반으로 나누고,

중간값==찾는값이 될 떄까지 작업을 반복합니다.

left와 right 변수를 설정하여 구간을 관리했고, 이를 코드로 나타내면 위와 같습니다.