백준 - 1920번(수 찾기)

문제 출처: https://www.acmicpc.net/problem/1920

문제

• N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

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

/**
 * 1. 이진탐색이다.
 * 2. 시간복잡도 -> O(logN) 가능
 * 3. 2^31 -> int 가능
 */

public class Main {

    private static int[] num;
    private static boolean ans;

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(reader.readLine());
        num = new int[N];

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        for (int i = 0; i < N; i++) {
            num[i] = Integer.parseInt(tokenizer.nextToken());
        }

        Arrays.sort(num);

        int M = Integer.parseInt(reader.readLine());
        tokenizer = new StringTokenizer(reader.readLine());
        for (int i = 0; i < M; i++) {
            ans = false;
            binarySearch(0, N - 1, Integer.parseInt(tokenizer.nextToken()));
            sb.append(ans ? 1 : 0).append("\n");
        }

        System.out.println(sb);
    }

    private static void binarySearch(int start, int end, int target) {
        if (start == end) {
            ans = num[start] == target;
            return;
        }

        int mid = (start + end) / 2;

        if (num[mid] < target) binarySearch(mid + 1, end, target);
        else binarySearch(start, mid, target);
    }

}

• 이진탐색 알고리즘 복습이다.
• 간단한 개념인데, 자주 사용하지 않아 생소하였다.
• 보통 while 문을 사용하여 (left <= right) 조건을 사용해서 하는 사람들이 많은 것 같은데 뭔가 한번에 로직이 와닿지 않았다.
• 참고하는 유튜브 강의에서 소개된 방법으로 재귀 함수를 사용하는 것으로 풀었는데 이것이 뭔가 더 명확한 것 같다.
• 중간값을 찾아서 만약 이 중간값이 타겟보다 작다면 타겟보다 큰 부분을 보아야 하므로 start를 mid + 1로 한다.
• 만약, 중간값이 타겟보다 작거나 같다면, 같은 경우도 처리해야 하므로 end에 mid를 넘겨준다.
• 값이 존재하든, 존재하지 않든 마지막이라면 처음과 끝 변수가 같은 자리를 가리키게 된다.