[白俊]#1920首検索

1694 ワード
白駿 boj テキストリンク

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

📃 質問する


N個の整数A[1]、A[2]、...、およびA[N]が与えられた場合、Xという整数が存在するか否かを判定するプログラムを作成してください.

📥 入力


第1行は自然数N(1≦N≦100000)を与える.次の行には、N個の整数A[1],A[2],...,A[N]が与えられる.次の行はM(1≦M≦100000)を与える.次の行はM個の数を与え、これらの数がAに存在するかどうかを見つければよい.すべての整数の範囲は、231未満の-231以上です.

📤 しゅつりょく


M行に答えを出力します.存在する場合は1を出力し、存在しない場合は0を出力します.

💡 に近づく

  • 配列で特定の数字を検索するアルゴリズムはバイナリ検索です!
  • バイナリ検索は、sortを先に行う必要があります.

    • 📍 コード#コード#

    import java.util.Scanner;
import java.util.Arrays;

class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int a[] = new int[n];

        for(int i = 0; i<n; i++ ) {
            a[i] = sc.nextInt();
        }

        Arrays.sort(a);

        int m = sc.nextInt();
        int b[] = new int[m];

        for (int i = 0; i<m; i++) {
            b[i] = sc.nextInt();
            System.out.println(binarySearch(a, b[i]));
        }
        sc.close();
    }
    
    private static int binarySearch(int[] a, int n) {
        int first = 0;
        int last = a.length -1;
        int mid = 0;

        while (first <= last) {
            mid = (first + last) /2;

            if (n == a[mid]) return 1;
            else {
                if (n < a[mid]) last = mid -1;
                else first = mid + 1;
            } 
        }
        return 0;
    }
}
    难しくなく解けたルル~!
    log4j.propertiesプロファイル
    Ubuntu国内ソースの交換