백준/1920번/Java - 수 찾기 (이진탐색)

 

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

1920번: 수 찾기

---

이진탐색은 배열이 정렬된 상태에서 원하는 값을 찾을 때 사용할 수 있는 알고리즘이다.

 

정렬된 배열의 중앙에 위치한 값을 선택하고, 찾고자 하는 수(target)과 그 크기를 비교한다.

배열 A의 길이가 N이라면 중앙값의 위치(mid)는 0(start) + N-1(end) 을 2로 나눈 수가 된다.

중앙값이 타겟보다 크다면, 찾고자 하는 수는 중앙값 기준으로 왼쪽에 있으므로

다음 탐색에서는 start ~ mid -1 사이에서 타겟을 찾으면 된다. 

 

반대로 중앙값이 타겟보다 작다면, 타겟은 중앙값 기준으로 오른쪽에 있으므로

다음 탐색에서는 mid + 1 ~ end 사이에서 타겟을 찾으면 된다.

 

이러한 탐색을 반복하다가 A[mid] = target이 되는 순간 탐색을 종료하면 된다.

 

단, 반복은 start가 end보다 커지면 중지해야 한다. 

이진 탐색을 계속 반복하다보면 start 포인터와 end 포인터는 점점 가까워지는데 (탐색범위를 점점 좁히니까)

두 포인터가 서로 교차하였다는 것은 더 이상 탐색할 범위가 없다는 뜻이기 때문이다.

 

1920번 문제는 이러한 이진 탐색을 구현하면 쉽게 풀 수 있다.

주어진 배열을 Arrays.sort()하여 오름차순 정렬하고 이진탐색으로 주어진 수들을 찾으면 된다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int[] A;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        A = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A); //O(nlogn)
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int start = 0;
        int end = N-1;
        for(int i=0; i<M; i++) {

            int target = Integer.parseInt(st.nextToken());
            if(binarySearch(start, end, target)){
                bw.write("1\n");
            } else {
                bw.write("0\n");
            }
        }

        br.close();
        bw.flush();
        bw.close();
    }

    private static boolean binarySearch(int start, int end, int target) {
        boolean find = false;
        while (start <= end) {
            int mid = (start + end) / 2;
            if(A[mid] > target) {
                end = mid -1;
            }
            else if(A[mid] < target) {
                start = mid + 1;
            }
            else {
                //A[mid] == target
                find = true;
                break;
            }
        }
        return find;
    }
}