Java, アルゴリズム

Java標準APIで二分探索(バイナリサーチ)

はじめに

Javaで二分探索(バイナリサーチ)をやりたい場合、標準API(Arrays.binarySearch())が用意されているため、これを活用するのが最も簡単な実装方法です。(だと思う、知らんけど)
というわけで、この記事ではArrays.binarySearch()について調べた内容をまとめてみようと思います。

概要

まずはjavadocを見る
https://docs.oracle.com/javase/jp/11/docs/api/java.base/java/util/Arrays.html#binarySearch(int%5B%5D,int)

public static int binarySearch(int[] a, int key)

バイナリ・サーチ・アルゴリズムを使用して、指定されたint値の配列から指定された値を検索します。 この呼出しの前に、sort(int[])メソッドで配列をソートする必要があります。 リストがソートされていない場合、結果は定義されません。 指定された値を持つ要素が配列に複数ある場合には、どれが検索されるかについての保証はありません。

パラメータ:
a - 検索される配列
key - 検索される値

戻り値:
配列内に検索キーがある場合は検索キーのインデックス。それ以外の場合は(-(挿入ポイント) - 1)。 挿入時点は、そのキーが配列に挿入される時点として定義される。つまり、そのキーよりも大きな最初の要素のインデックス。配列内のすべての要素が指定されたキーよりも小さい場合はa.length。 これにより、キーが見つかった場合にのみ戻り値が>= 0になることが保証される。

ざっくりまとめるとパラメータとしては検索対象の配列検索値を指定。
渡す配列はソート済みである必要があります。(これはバイナリサーチの前提条件ですね)
戻り値は検索値が見つかった場合、その配列要素のインデックスが返却される。見つからなかった場合はその値の挿入位置(挿入すると仮定して下から何番目の大きさか)がマイナス値で返ってきます。
マイナスは単にヒットしなかったことを表しているだけなので、後続処理で使用する場合はMath.abs()などで絶対値に変換するなりしよう。

検証

Arrays.binarySearch()の動作を確認するため、簡単な検証コードを書きました。


import java.util.Arrays;
import static java.lang.System.out;

public class Main {

    public static void main(String[] args) {

        int[] arr = new int[]{-4,-3,-2,2,3,4};

        out.println("Case01: " + Arrays.binarySearch(arr, -5));
        out.println("Case02: " + Arrays.binarySearch(arr, -4));
        out.println("Case03: " + Arrays.binarySearch(arr, -3));
        out.println("Case04: " + Arrays.binarySearch(arr, -2));
        out.println("Case05: " + Arrays.binarySearch(arr, -1));
        out.println("Case06: " + Arrays.binarySearch(arr, 0));
        out.println("Case07: " + Arrays.binarySearch(arr, 1));
        out.println("Case08: " + Arrays.binarySearch(arr, 2));
        out.println("Case09: " + Arrays.binarySearch(arr, 3));
        out.println("Case10: " + Arrays.binarySearch(arr, 4));
        out.println("Case11: " + Arrays.binarySearch(arr, 5));
    }
}

実行結果

Case01: -1
Case02: 0
Case03: 1
Case04: 2
Case05: -4
Case06: -4
Case07: -4
Case08: 3
Case09: 4
Case10: 5
Case11: -7

コードと結果を突き合わせて見ていくと
Case01:-5は配列に存在せず、配列内のどの値よりも小さいので-1。ヒットしない場合のインデックスは0はじまりではなく、-1,-2,…となっていくので注意。
Case02:-4は配列の最小値にヒットするため、0が返却される。
Case03、Case04:ヒットした配列要素のインデックスを返却。
Case05〜Case07:-1〜1は配列に存在しない&どれも挿入した場合、下から4番目の大きさになるため-4。
Case08〜Case10:ヒットした配列要素のインデックスを返却。
Case11:5は配列に存在せず、配列内(要素数6)のどの値よりも大きいので-7。

所感

ヒットしない場合の返却値が絶対値で見て1はじまりになっていて、0はじまりの配列の文化と噛み合わないことがありそうなので、これを使って後続の処理を書く場合は要注意かもしれない。Arrays.binarySearch()は今回使用したメソッド以外にもパラメータ違いのメソッドが多数あるので実際に使用するときはjavadocを確認すべし。
https://docs.oracle.com/javase/jp/11/docs/api/java.base/java/util/Arrays.html

コメントする(リンクを含む場合、承認待ちになります)

メールアドレスが公開されることはありません。