naoppyの日記

自分が欲しいなと思った記事を書きます。

Javaでの二分探索、lower_boundとupper_boundの実装

こんにちは、naoppyです。 AtCoderでこの問題 C - Snuke Festival を解いているときに、Javaの二分探索が能力不足だと感じた為、自作することにしました。

Javaの二分探索

Collections (Java Platform SE 8) これを見ればわかるのですが、Javaの二分探索は引数にlist、key、Comparatorをとります。

戻り値はintで、見つかった場合はkeyのインデックス(複数のkeyがリストに含まれている場合、どれが返るかは保障されない)

見つからなければ(-(挿入ポイント) - 1)が返ります。

(-(挿入ポイント) - 1)、これはどういうことかというと、見つからなければ必ず戻り値は0未満、負数になるので、見つかったかどうかがわかります。

ここから挿入ポイントを復元するには逆の操作、(-(戻り値+1))をしてやればいいです。

もう少し考えてみましょう。1足してマイナスにする=1足して2の補数を取る=1足してbit反転してから1を足す=bit反転だけでいいことになります。

よって(-(挿入ポイント) - 1)から挿入ポイントを得るには~value(~はbit反転)でいいことがわかります。

lower_bound、upper_boundとは

C++のstd::lower_bound、std::upper_boundのことです。 lower_bound関数は指定した値以上の要素が最初に現れる位置を返し、upper_bound関数は指定した値より大きいの要素が最初に現れる位置を返します。

実装の方針としては、二分探索の引数の3番目、Comparatorを自分でうまくかくことで、比較的簡単に書こうと思います。

ラムダ式を使うことでさらに簡単に書けます。

実装

まず、Comparatorだけの実装をお見せします。

Comparator<Integer> lower = (x, y) -> x.compareTo(y) >= 0 ? 1 : -1;
Comparator<Integer> upper = (x, y) -> x.compareTo(y) > 0 ? 1 : -1;

これをCollections.binarySearch(list, key, Comparator)の第3引数にわたしてあげれば、それぞれlower_bound、upper_boundになるわけです。

ですが、このComparatorを渡したbinarySearchは必ず負数を返すことになります。よって値が存在したかどうかはわかりません。

戻り値は必ず~を付けてbit反転しましょう。

使用例

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class binarySearch {
    final static int[] array = { 2, 2, 3, 4, 4, 4, 6, 6 };
    final static List<Integer> list = int2List(array);

    public static void main(String[] args) {
        //lower_bound
        int lowerResult = ~Collections.binarySearch(list, 4, (x, y) -> x.compareTo(y) >= 0 ? 1 : -1);
        System.out.println(lowerResult);// => 3
        //upper_bound
        int upperResult = ~Collections.binarySearch(list, 4, (x, y) -> x.compareTo(y) > 0 ? 1 : -1);
        System.out.println(upperResult);// => 6
    }

    //int配列をList<Integer>に変換するヘルパーメソッド
    static List<Integer> int2List(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }
        Collections.sort(list);
        return list;
    }
}

最後に

  • ~が見にくい。見落としやすくバグを生む危険がある。

  • binarySearchの引数に直接ラムダ式を渡すのは、可読性の面から良くない。 Comparatorを作って、それを渡す方が良い。

  • 値の存在を確認するのは、普通のbinarySearchを使って戻り値が正かどうかを見るしかない。

など、気を付けるべき点がいくつかある。

それなりに綺麗にかけたので満足。