Java 1920 수 찾기

 

풀이 :

이분탐색을 하는 메서드를 구현한 뒤 둘째줄에서 입력받은 배열에 네번째 줄에서 받은 배열의 숫자가 있는지 이분 탐색을 이용하여 확인한 뒤 출력하면 풀 수 있는 문제다.

이분 탐색이란, 처음부터 끝까지 비교하며 찾는 선형검색 방법과는 다르게 배열의 시작부터 끝까지의 크기에서 2를 나누어 기준을 잡은 뒤 타겟값과 기준 값을 비교하여 시작과 끝을 좁혀가며 원하는 값을 찾는 방법으로 글로 보는 거보단 그림과 코드로 보는 편이 이해가 더 잘되었다.

 

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

public class Main{
    public static int binarySearch(int[] arr, int target){
        int start = 0;
        int end = arr.length - 1;
        while(start <= end){
            int mid = (start + end)/2;
            if(target < arr[mid]){
                end = mid -1;
            }else if(target > arr[mid]){
                start = mid + 1;
            }else {
                return mid;
            }
        }
        return -1;
    }
    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 stt = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < m; i++){
            int target = Integer.parseInt(stt.nextToken());
            if(binarySearch(arr, target) >= 0){
                sb.append(1 + "\n");
            }else {
                sb.append(0 + "\n");
            }
        }
        System.out.print(sb);
    }
}