BohYoh.comトップページへ
Java FAQ
目次

ソートされた配列からの探索法を教えてください。

　ソートされた配列からの２分探索は、java.util.Arraysクラスで提供されるbinarysearchメソッドで行えます。その概略を以下に示します。

static int binarySearch(byte[] a, byte key) byte値の配列aからkeyと一致する要素を探索。
static int binarySearch(char[] a, char key) char値の配列aからkeyと一致する要素を探索。
static int binarySearch(double[] a, double key) double値の配列aからkeyと一致する要素を探索。
static int binarySearch(float[] a, float key) float値の配列aからkeyと一致する要素を探索。
static int binarySearch(int[] a, int key) int値の配列aからkeyと一致する要素を探索。
static int binarySearch(long[] a, long key) long値の配列aからkeyと一致する要素を探索。
static int binarySearch(Object[] a, Object key) 要素の「自然順序付け」に従って、オブジェクトの配列aからkeyと一致する要素を探索。
sstatic int binarySearch(short[] a, short key) short値の配列aからkeyと一致する要素を探索。
static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) コンパレータが示す順序に従って、オブジェクトの配列aからkeyと一致する要素を探索。

　int型の配列に値を読み込んで、その値を昇順にソートして表示するプログラムを以下に示します。
昇順に入力してください。
要素数：7
x[0]：15
x[1]：27
x[2]：39
x[3]：77
x[4]：92
x[4]：108
x[4]：121
探す値：39
その値はx[4]にあります。
// Arrays.binarySearchによる２分探索

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

class BinarySearchTester {

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);

        System.out.print("要素数は：");
        int num = stdIn.nextInt();
        int[] x = new int[num];     // 長さnumの配列

        System.out.println("昇順に入力してください。");

        System.out.print("x[0]：");     // 先頭要素の読込み
        x[0] = stdIn.nextInt();

        for (int i = 1; i < num; i++) {
            do {
                System.out.print("x[" + i + "]：");
                x[i] = stdIn.nextInt();
            } while (x[i] < x[i - 1]);  // 一つ前の要素より小さければ再入力
        }
        System.out.print("探す値：");       // キー値の読込み
        int ky = stdIn.nextInt();

        int idx = Arrays.binarySearch(x, ky);   // 配列xから値がkyの要素を探索

        if (idx < 0)
            System.out.println("その値の要素は存在しません。");
        else
            System.out.println("その値は" + "x[" + idx + "]にあります。");
    }
}

戻る
BohYoh.comロゴ