[백준] 수 찾기 1920번 - Java

[백준] 수 찾기 1920번

나의 풀이

public class FindNumber {
    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[] n_nums = Arrays.stream(br.readLine().split(" ")).mapToInt(i -> Integer.parseInt(i)).sorted().toArray();
        int M = Integer.parseInt(br.readLine());
        int[] m_nums = Arrays.stream(br.readLine().split(" ")).mapToInt(i -> Integer.parseInt(i)).toArray();

        for(int i = 0; i < M; i++) {
            if(binary_search(n_nums, m_nums[i], 0, N - 1)) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
    }

    static private boolean binary_search(int[] arr, int target, int start, int end) {
        while(start <= end) {
            int mid = (start + end) / 2;

            if(arr[mid] == target) {
                return true;
            } else if(arr[mid] > target) {
                end = mid - 1;
            } else if(arr[mid] < target) {
                start = mid + 1;
            }
        }

        return false;
    }
}

• 이분 탐색(Binary Search):
  • 이분 탐색을 하기 전에 리스트는 오름차순 정렬이 되어 있어야 한다.
  • 해당 리스트의 중간 값을 기준으로 리스트의 시작과 끝을 조절하는 방식이다.
  • 중간 값과 같으면 해당 해당 인덱스를 반환한다.
  • 중간 값 보다 찾는 값이 더 크다면 시작점을 중간 + 1 로 옮기고 다시 탐색을 시작한다.
  • 중간 값 보다 찾는 값이 더 작다면 끝점을 중간 - 1 로 옮기고 다시 탐색을 시작한다.
  • 위 과정을 값을 찾을 때 까지 반복하다가 시작점이 끝점을 초과하게 되면 값이 없는 것으로 반복을 종료한다.
• 이분 탐색만 구현할 줄 알면 충분히 풀 수 있는 문제다.