Java – BinarySearch

今回は、JavaでBinarySearchを作成してみたいと思います。

上記は9を検索する場合のBinarySearchとLinearSearchの例です。

前提条件

• BinarySearchを行うデータは必ずソートされていなければならないです。

BinarySearch

public static int binarySearch() {

    int[] n = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int target = 8;

    int start = 0;
    int last = n.length - 1;

    do {
        int center = (start + last) / 2; // ①
        if (n[center] == target) { // ②
            return center;
        } else if (n[center] < target) { // ③
            start = center + 1;
        } else { // ④
            last = center - 1;
        }
    } while (start <= last); // ⑤

   return -1; // ⑥
}

BinarySearchを作成するときは、３つの変数（start、last、center）が必要です。

上記の例は「8」を検索しています。

1. centerのIndexを「(start ＋ last) / 2」をして取得します。
   1. centerは検索対象と比較するためとcenterを基準でstartとlastを変えます。
2. 検索対象と一致しているかを判定します。
3. centerのデータが検索対象より小さい場合は、「start = center + 1」をします。
   1. 上記の例ではループが1回目に検索範囲が「6、7、8、9」となります。
4. centerのデータが検索対象より大きい場合は、「last = center – 1」をします。
   1. 「5、6、7、8、9」は検索する必要がないです。
5. 見つからなかった場合は、startがlastより値が大きくなりますので、条件として「start <= last」で判定をおこないます。
6. 見つからなかった場合、-1を返します。

do-whileを使った理由としては、whileを使うよりループ判定(start <= last)が1回少なく動くからです。

Arrays.binarysearch

Javaでは「Arrays.binarysearch」を提供しているので、アルゴリズムを求めるコーディング試験意外（業務？？）では「Arrays.binarysearch」を利用した方が楽で、可視性も良いでしょう。

提供メソッドについてはこちらをご参考ください。