백준 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;

public class Main{
    public static int check(int[] a, int x){
        int start=0;
        int end=a.length-1;

        while(true){
            int mid=(start+end)/2;

            if(a[mid]==x)
                return 1;
            else if(a[mid]<x)
                start=mid+1;
            else
                end=mid-1;

            if(end<start)
                return 0;
        }
    }

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

        int n=Integer.parseInt(br.readLine());   //N 입력
        int[] a=new int[n]; //N개의 정수를 가진 A 배열
        String s=br.readLine();
        StringTokenizer st=new StringTokenizer(s);
        for(int i=0; i<n; i++)
            a[i]=Integer.parseInt(st.nextToken());
        Arrays.sort(a);

        int m=Integer.parseInt(br.readLine());   //M 입력
        int[] mList=new int[m];  //M개의 정수를 가진 배열
        s=br.readLine();
        st=new StringTokenizer(s);
        for(int i=0; i<m; i++) {
            mList[i] = Integer.parseInt(st.nextToken());
            System.out.println(check(a, mList[i]));
        }
    }
}

---

해결 과정

1. A 배열에 대해서 M개의 수가 각각 포함이 돼있는 지 탐색하는 것이기 때문에 A 배열을 오름차순으로 정렬하고 M개의 수를 하나씩 Binary Search로 확인했다. start, end는 각각 A 배열의 최초 인덱스, 최대 인덱스로 잡아두고 A[ (start+end)/2 ] 와 대소 관계를 비교해서 탐색했다.

2. 😁