はじめに

書籍「新・明解 Javaで学ぶアルゴリズムとデータ構造」第3章-3 2分探索より、Java を書く上で覚えておきたい定石があったので二分探索についても含めて本記事にまとめてみました。

Java による二分探索

Java は配列から二分探索を行うメソッドを標準ライブラリとして提供しています。
java.util.Arrays クラスに所属する binarySearch メソッドです。

参考: https://docs.oracle.com/javase/jp/8/docs/api/java/util/Arrays.html

上記参考リンク先にあるように binarySearch メソッドは様々な要素型に対応できるよう、数多く定義されています。いずれも、昇順にソート済みの配列からキー値の要素を二分探索します ( 昇順ソートされていない場合の結果は定義されていません ) 。
配列内に検索キーがある場合は検索キーのインデックスを、存在しなかった倍は (-(挿入ポイント) - 1) を返します。

今回注目するのは次の二つです。

static int binarySearch(Object[] a, Object key)
static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

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

自然な順序で要素の大小関係を判定します。自然順序付けについては以下を参考にどうぞ。

参考: https://docs.oracle.com/javase/jp/8/docs/api/java/lang/Comparable.html

上記参考リンク先の Comparable インターフェイスを実装している型の配列であれば、このメソッドを使って簡単に二分探索するコードを書くことができます。

自然順序付けのできるクラス定義のちょっとした定石

つまり、自作のクラスに関しても、この Comparable インターフェイスを実装すれば自然順序付けを定義することができ、このメソッドを使用することができるようになります。以下をちょっとした定石として覚えておくと良いでしょう。

自然順序付けのできるクラス.java

public class Hoge implements Comparable<Hoge> {
    // フィールドやメソッドなど

    @Override
    public int compareTo(A c) {
        // this が c より大きければ正の値を、
        // this が c より小さければ負の値を、
        // this が c と等しければ 0 を返す。
    }

    @Override
    public boolean equals(Object c) {
        // this が c と等しければ true を、
        // this が c と等しくなければ false を返す。
    }
}

この時、「 conpareTo メソッドが 0 を返す時は equals メソッドが true を返し、 compareTo メソッドが 0 以外を返す時は equals メソッドが false を返す」というように整合性が取れるようにすると良いでしょう。

static int binarySearch(T[] a, T key, Comparator super T> c)

このメソッドは、自然な順序ではない順序で並べられた配列から二分探索する時に使用できます。ジェネリックなメソッドなので、配列の要素の方はなんでも OK です。

ただし、各要素の大小関係をどのように判定するのかをメソッドに通知しなければならなりません。そのために、第三引数に java.util.Comparator インターフェースを実装したクラスのインスタンスを渡します。

コンパレータを定義するちょっとした定石

例えば、クラス Fuga のコンパレータは次のように定義できます。これもちょっとした定石として覚えておくと良いでしょう。

クラス内部でコンパレータを定義.java

public class Fuga {
    // フィールドやメソッドなど

    public static final Comparator<Fuga> COMPARATOR = new Comp();

    private static class Comp implements Comparator<Fuga> {
        public int compare(Fuga d1, Fuga d2) {
            // d1 が d2 より大きければ正の値を、
            // d1 が d2 より小さければ負の値を、
            // d1 が d2 と等しければ0を返す。
        }
    }
}

Fuga.COMPARATOR を binarySearch メソッドの第三引数として渡すことで、定義したコンパレータを元に大小関係を判断して、 Fuga 型の配列の二分探索を行えます。