Javaでデータの探索を実装する

基本情報技術者試験に向けて勉強しています。今回はJavaでデータの探索を行う方法についてまとめます。

Arrays.binarySearchによる二分探索

標準ライブラリでは、java.utilパッケージに含まれるArraysクラスを用いることで配列からの探索を行うことができます。

  • static int binarySearch(int[] a, int key)
    バイナリサーチアルゴリズム(二分探索法)を使用して、指定されたint値の配列から指定された値を検索します。

動作確認

確認用のクラスを作成し、mainメソッドに以下を記述してください。

public static void main(String[] args) {
    int[] array = {1, 3, 4, 5, 7, 11, 14, 20, 23, 28};

    int index;
    index = Arrays.binarySearch(array, 4);
    System.out.println(index);
    index = Arrays.binarySearch(array, 13);
    System.out.println(index);
}

実行結果:

2
-7

配列中に検索データがある場合はその添え字、ない場合はマイナスの値が返されました。
arrayに設定している配列を見ると、小さい順に値が並んでいることがわかります。二分探索法はこのように配列の各要素が順番に並んでいることを前提として、高速にデータを探索するアルゴリズムになっています。

線形探索法

線形探索法(リニアサーチ、linear search)とは、配列を先頭からひとつずつ順番に見ていき探索データがあるかを確認する、というものになります。何も難しいことはなく、普段よく書いているfor文やwhile文で要素を一つずつ確認していくようなプログラムが線形探索法にあたります。

それでは線形探索法を実現するプログラムを作成しましょう。メソッドの引数と戻り値は標準ライブラリのArrays.binarySearchメソッドに合わせて以下の通りとします。

  • static int linearSearch(int[] a, int key)
    配列aにkeyがあるか探索し、そのインデックスを返します。keyが配列中にない場合は-1を返します。

LinearSearchクラスを作成し、以下のメソッドを記述してください。

public class LinearSearch {
    public static int linearSearch(int[] a, int key) {
        int i = 0;
        while (i < a.length) {
            if (a[i] == key) {
                return i;
            }
            i = i + 1;
        }
        return -1;
    }
}

動作確認

動作確認用のクラスを作成し、mainメソッドに以下を記述します。

public static void main(String[] args) {
    int[] array = {1, 3, 4, 5, 7, 11, 14, 20, 23, 28};

    int index;
    index = LinearSearch.linearSearch(array, 4);
    System.out.println(index);
    index = LinearSearch.linearSearch(array, 13);
    System.out.println(index);
}

実行結果:

2
-1

番兵法

線形探索法は見てきたように非常にシンプルです。ただし、次のように一度のループ中に比較処理が2回あるという問題があります。

  • 確認対象の配列要素が探索値かの確認
  • 配列の添え字が配列の範囲外かの確認

番兵法という手法を用いることにより比較処理を1回にすることが可能です。番兵法のアルゴリズムは以下のようになります。

  1. 配列の末尾に探しているデータを追加する
  2. 添え字を0とする
  3. 配列[添え字]が探しているデータかを調べる。探しているデータの場合は6.に飛ぶ
  4. 添え字に1を加える
  5. 2.に戻る
  6. 添え字が本来の配列の大きさ未満なら探索成功、そうでないなら探索失敗

線形探索法と番兵法をフローチャートで比較してみます。

  • 線形探索法

72106-1

  • 番兵法

72201

線形探索法では繰り返し処理の中で2回比較処理を行っています。対して、番兵法では繰り返し処理の中では1回しか比較処理を行わず、繰り返し処理を抜けた後で最後に比較処理をもう1回行っています。

番兵法では繰り返し処理中に添え字が範囲外かのチェックをしなくていいという特徴があります。これにより処理時間が短くなることが期待できます。ただし、番兵法では本来の配列にもうひとつ要素を追加する必要があります。そのため、Javaのように動的に配列要素を追加できないプログラミング言語では利用することはできません。線形探索を行う場合でも番兵法のような改良を加えることで処理の高速化が行えるということを覚えておいてください。

二分探索法

二分探索法(バイナリサーチ、binary search)とは、「二分」の名前が示すように探索範囲を二分の一にしていくことで高速に探索を行う手法です。

二分探索法でデータを検索してみましょう。「4」を検索することを考えます。線形探索法では配列の先頭からデータがあるか確認しましたが、二分探索法では配列の真ん中から調べます。

73102

a[4]は「4」ではありませんでした。また、a[4]と「4」を比較すると4 < 7という関係が成り立っていることがわかります。二分探索法ではこの際、a[4]より後の範囲(右半分)は調べる必要がないと判断します。このように判断していいのは配列が小さい順に並んでいるため、a[4]以降にあるデータはかならず、4 < a[i]となるためです。

次に、 残ったa[0]~a[3]について、同様のその真ん中(4要素なので真ん中ではありませんが)のa[1]が「4」か調べます。a[1]は「4」ではありませんでした。今度は、3 < 4という関係になっています。この場合、a[1]より前(左半分)はもう調べる必要がないと判断できます。

73104

続いて、a[2]~a[3]の真ん中(2要素なので真ん中ではありませんが)のa[2]が「4」か調べます。a[2]は「4」なので配列中に「4」があることがわかりました。

73105

二分探索法のアルゴリズムは以下のようになります。

  1. 探索範囲の下限lowを0、上限highをn-1とする(nは配列の要素数)
  2. 上限と下限の真ん中を求める(mid = (low + high) / 2、小数点以下切り捨て)
  3. 配列[mid]が探しているデータであれば探索終了
  4. 探しているデータ < 配列[mid]の場合、high = mid - 1とする(探索範囲を左半分にする)
  5. 配列[mid] < 探しているデータの場合、low = mid + 1とする(探索範囲を右半分にする)
  6. high < lowとなった場合は探索を終了する。そうでなければ2.に戻って繰り返す

上記のアルゴリズム通りに探索を行うと、上で説明した図の通りになることを確認してください。また、データが見つからない場合はhigh < lowという状況になることも確認してください。

それでは二分探索法を実現するプログラムを作成します。メソッドの引数と戻り値は標準ライブラリのArrays.binarySearchメソッドに合わせて以下の通りとします。

  • static int binarySearch(int[] a, int key)
    配列aにkeyがあるか探索し、そのインデックスを返します。keyが配列中にない場合は-1を返します。

BinarySearchクラスを作成し、以下のメソッドを記述してください。

public class BinarySearch {
    public static int binarySearch(int[] a, int key) {
        int low = 0;
        int high = a.length - 1;
        while (low <= high) {
            // 探索範囲の真ん中の要素をチェック
            int mid = (low + high) / 2;
            if (a[mid] == key) {
                return mid;
            } else if (key < a[mid]) {
                // 探索範囲を左半分にする
                high = mid - 1;
            } else if (a[mid] < key) {
                // 探索範囲を右半分にする
                low = mid + 1;
            }
        }
        return -1;
    }
}

動作確認

新しくクラスを作成し、mainメソッドに以下を記述します。

public static void main(String[] args) {
    int[] array = {1, 3, 4, 5, 7, 11, 14, 20, 23, 28};

    int index;
    index = BinarySearch.binarySearch(array, 4);
    System.out.println(index);
    index = BinarySearch.binarySearch(array, 13);
    System.out.println(index);
}

実行結果:

2
-1

参考資料
スクールの教科書