[JAVA] 백준 1920 이진 탐색

 

1920번: 수 찾기

문제

N개의 정수가 주어졌을 때, X라는 정수가 있는지 없는지 여부를 출력하시오.

풀이

정렬

        A = new int[N];
        for(int i=0; i<N; i++){
            A[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(A);

먼저 이진 탐색을 사용하기 위해서 값을 받은 후 정렬해주었다.

이진 탐색 구현

public static int binarySearch(int t, int start, int end){
        int mid = start + (end - start) / 2;
        if(end - start < 1 && A[mid] != t) return 0;

        if(A[mid] == t ) return 1;
        return A[mid] > t ? binarySearch(t, start, mid) : binarySearch(t, mid+1, end);
}

이진 탐색을 다음과 같이 재귀로 구현하였다.

1. 중심값을 구한다.
2. 만약 현재 탐색할 영역이 1개 밖에 없고, 그 값이 타겟값과 다르다면 존재하지 않는 값이므로 0을 출력
3. 만약 중심 값이 타겟값과 같다면 1을 출력
4. 중심 값이 타겟값보다 크다면 start ~ mid 값을 다시 탐색
5. 중심 값이 타겟값보다 작다면 mid+1 ~ end 값을 탐색

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static int[] A;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        A = new int[N];
        for(int i=0; i<N; i++){
            A[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(A);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++){
            sb.append(binarySearch(Integer.parseInt(st.nextToken()), 0, N-1)).append("\n");
        }
        System.out.println(sb);

        br.close();
    }
    public static int binarySearch(int t, int start, int end){
        int mid = start + (end - start) / 2;
        if(end - start < 1 && A[mid] != t) return 0;

        if(A[mid] == t ) return 1;
        return A[mid] > t ? binarySearch(t, start, mid) : binarySearch(t, mid+1, end);
    }

}

결과