探索の線形法の基本と番兵法、二分法

こんにちは。「Javaを復習する初心者」です。今回は探索の線形法の基本と番兵法、二分法を書いてみました。参考にしたのは日経ソフトウェア2017年5月号に載っていた「トランプでおぼえるアルゴリズム」です。C言語で載っていたのをJavaにして、探索の途中経過を出力するようにしました。

前提として、int型の配列を探索するとします。指定して番号が含まれているかどうかを調べるのを目的とします。

以下のメソッドを実装して、途中経過を出力することをやりました。

public boolean search(int nums[], int target)

nums[]が探索する配列、targetが見つける値です。見つかった場合、trueを返却します。

1 線形法の基本
2 線形法の番兵法
3 二分法

線形法の基本

線形法の基本的なアルゴリズムは配列の先頭から順番に探索することです。

具体的なソースは以下です。

ソース

package nikkei201705;

import java.util.Arrays;

public class SearchTest1 {

    public static void main(String[] args) {
        new SearchTest1().test();
    }

    public void test() {
        int[] nums = { 3, 4, 1, 5, 2, 6};
        boolean res;

        res = search(nums, 5);
        System.out.println(res);

        System.out.println("--");

        res = search(nums, 7);
        System.out.println(res);
    }

    public boolean search(int nums[], int target) {
        System.out.println("配列:" + Arrays.toString(nums));
        System.out.println("探す値:" + target);

        for (int i = 0; i < nums.length; i ++) {
            if (nums[i] == target) {
                System.out.println(i + "番目に見つかりました。");
                return true;
            }
            System.out.println(i + "番目は違いました。");
        }
        return false;
    }

}

結果

配列:[3, 4, 1, 5, 2, 6]
探す値:5
0番目は違いました。
1番目は違いました。
2番目は違いました。
3番目に見つかりました。
true
--
配列:[3, 4, 1, 5, 2, 6]
探す値:7
0番目は違いました。
1番目は違いました。
2番目は違いました。
3番目は違いました。
4番目は違いました。
5番目は違いました。
false

配列の最後まで探索しますが、途中で値が見つかればそこで繰り返し処理を終了しています。

線形法の番兵法

末尾に探索対象の数値を追加した配列を使う方法です。元々の配列に対象の数値がなくても、最後に必ずヒットするというのが特徴のようです。

ソース

package nikkei201705;

import java.util.Arrays;

public class SearchTest2 {

    public static void main(String[] args) {
        new SearchTest2().test();
    }

    public void test() {
        int[] nums = { 3, 4, 1, 5, 2, 6};
        boolean res;

        res = search(nums, 5);
        System.out.println(res);

        System.out.println("--");

        res = search(nums, 7);
        System.out.println(res);
    }

    public boolean search(int nums[], int target) {
        System.out.println("配列:" + Arrays.toString(nums));
        System.out.println("探す値:" + target);

        int[] tempNums = new int[nums.length + 1];
        System.arraycopy(nums, 0, tempNums, 0, nums.length);
        tempNums[tempNums.length - 1] = target;
        System.out.println("番兵追加:" + Arrays.toString(tempNums));

        int index = 0;
        while (tempNums[index] != target) {
            index ++;
        }

        System.out.println("要素番号:" + index);
        return index < tempNums.length - 1;
    }

}

結果

配列:[3, 4, 1, 5, 2, 6]
探す値:5
番兵追加:[3, 4, 1, 5, 2, 6, 5]
要素番号:3
true
--
配列:[3, 4, 1, 5, 2, 6]
探す値:7
番兵追加:[3, 4, 1, 5, 2, 6, 7]
要素番号:6
false

番兵が末尾に追加されているので、while文を使っています。繰り返し回数は気にしないという事です。要素番号が「配列の長さ – 1」の場合、元の配列には対象の値が見つからなかったということになります。

二分法

配列の要素が昇順に並んでいるのが前提です。イメージとしては数直線上の区間を中心を調べて、検索対象の方が小さい（大きい）なら、左側（右側）半分の区間に対して同様の操作をするという方法です。

ソース

package nikkei201705;

import java.util.Arrays;

public class SearchTest3 {

    public static void main(String[] args) {
        new SearchTest3().test();
    }

    public void test() {
        int[] nums = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19};

        System.out.println(Arrays.toString(nums));
        System.out.println(search(nums, 5));
        System.out.println(search(nums, 2));
    }

    public boolean search(int nums[], int target) {
        int indexOfResult = -1;
        int indexOFLeft = 0;
        int indexOFRight = nums.length -1;

        while (indexOfResult == -1 && indexOFLeft <= indexOFRight) {
            int middle = (indexOFLeft + indexOFRight) / 2;
            System.out.println("調査対象の要素番号" + middle);
            if (nums[middle] < target) {
                indexOFLeft = middle + 1;
            } else if (nums[middle] > target){
                indexOFRight = middle - 1;
            } else {
                indexOfResult = middle;
            }
        }

        return indexOfResult >= 0;
    }

}

結果

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
調査対象の要素番号4
調査対象の要素番号1
調査対象の要素番号2
true
調査対象の要素番号4
調査対象の要素番号1
調査対象の要素番号0
false

少ないステップで目的の値を見つけることができます。また、値がなかった場合の時も少ないステップで済みます。