オタク野郎の逆襲

普通のやつらの斜め上を行け

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#binarySearch