Algorithm | 二分探索(二分検索, Binary search)

二分探索(二分検索, Binary search)

昇順にソートされているリストで特定の値を探すとき、最初に中央の値を任意の値として選び、その値と探したい値の大小を比較する方式である。

メリット: 検索が繰り返されるたびに目標値を見つける確率が2倍になるため速い。
デメリット: ソートされたリストでしか使えない。

反復文を利用した方法

package com.devkuma.algorithum.programming.search.binary;

public class BinarySearchWhile {

    int search(int[] nums, int target) {
        int startIndex = 0;
        int endIndex = nums.length - 1;

        int middle = 1;

        while (startIndex <= endIndex) {
            middle = (startIndex + endIndex) / 2;
            if (nums[middle] == target)
                return middle + 1;
            else if (nums[middle] > target)
                endIndex = middle - 1;
            else
                startIndex = middle + 1;
        }
        return middle;
    }

    public static void main(String[] args) {
        BinarySearchWhile search = new BinarySearchWhile();

        int[] nums = {15, 28, 65, 67, 88, 92, 100, 150};
        int target = 28;
        int index = search.search(nums, target);

        if (index > 0) {
            System.out.println(target + "은 " + index + "번째 있습니다.");
        } else {
            System.out.println(target + "은 없습니다.");
        }
    }
}

実行結果:

5은 2번째 있습니다.

再帰関数を利用した方法

package com.devkuma.algorithum.programming.search.binary;

public class BinarySearchRecursion {

    int search(int arr[], int target, int startIndex, int endIndex) {
        if (startIndex > endIndex)
            return -1;

        int middle = (startIndex + endIndex) / 2;
        if (arr[middle] == target)
            return middle;
        else if (arr[middle] > target)
            return search(arr, target, startIndex, middle - 1);
        else
            return search(arr, target, middle + 1, endIndex);
    }

    public static void main(String[] args) {
        BinarySearchRecursion search = new BinarySearchRecursion();

        int[] nums = {15, 28, 65, 67, 88, 92, 100, 150};
        int target = 28;
        int startIndex = 0;
        int endIndex = nums.length - 1;

        int index = search.search(nums, target, startIndex, endIndex);

        if (index > 0) {
            System.out.println(target + "은 " + index + "번째 있습니다.");
        } else {
            System.out.println(target + "은 없습니다.");
        }
    }
}

実行結果:

28은 2번째 있습니다.

二分探索アルゴリズムの例の説明

上記の例で使った配列から28を探す二分探索を展開すると以下のようになる。

{ 15, 28, 65, 67, 88, 92, 100, 150 }
- 中央値: 88 -> 小さい -> { 15, 28, 65, 67 }
- 中央値: 43 -> 小さい -> { 15, 28 }
- 中央値: 28 -> 終了