1920 수 찾기 (JAVA)

• 이진 검색을 이용하면 정렬된 배열에 대해서 O(nlogn)의 시간복잡도로 탐색이 가능하다.

import java.util.Arrays;
import java.util.Scanner;

/* 1920 수 찾기 */
public class Main {
    static int binarySearch(int target, int[] arr){
        int lt = 0;
        int rt = arr.length-1;
        while(lt <= rt){
            int mid = (lt + rt) / 2;
            if(arr[mid] == target)
                return 1;
            else if(target < arr[mid])
                rt = mid - 1;
            else
                lt = mid + 1;
        }
        return 0;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; ++i)
            arr[i] = sc.nextInt();

        int m = sc.nextInt();
        int[] target = new int[m];
        for(int i=0; i<m; ++i)
            target[i] = sc.nextInt();

        Arrays.sort(arr);
        for(int i=0; i<m; ++i){
            int tg = target[i];
            System.out.println(binarySearch(tg, arr));
        }
    }
}