[Algorithm] binary search

binary search
O(NlogN)

정렬되어있는 상태에서 이진 탐색을 수행한다.

중앙값과 찾고자 하는 값을 비교하여 데이터의 크기를 절반씩 줄인다.

 

사진 출처 : https://hcr3066.tistory.com/23

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

1920번: 수 찾기

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

public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int N = Integer.parseInt(br.readLine());
            int[] A = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int M = Integer.parseInt(br.readLine());
            int[] findArr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            // 정렬
            Arrays.sort(A);

            // 이진 탐색
            for(int find : findArr){
                int start=0, end=N-1;
                boolean findCheck = false;
                while(start <= end){
                    int mid = ( start + end ) / 2;
                    if(A[mid] > find) end=mid-1;
                    else if(A[mid] < find) start=mid+1;
                    else findCheck=true;

                    if(findCheck) break;
                }

                System.out.println(findCheck? 1: 0);
            }
        } catch (Exception e) {
            System.out.println(e);
        }
    }
}