Javaで二分探索（LowerBound, UpperBound）
Java で二分探索を実装する際、わざわざ左端と右端と中央をループの中であれやこれやしなくても、クラスライブラリの java.util.Arrays に二分探索をおこなってくれるメソッドが存在しています。
仮に、以下のような配列があったとします。
int[] ar = {2,4,6,8,10,12,14,16,18,20};
この配列に対して通常の（Lower, UpperBoundでない）二分探索をおこなうには、以下のように記述します。
int[] ar = {2,4,6,8,10,12,14,16,18,20}; int a = Arrays.binarySearch(ar, 8); // 出力：3 int b = Arrays.binarySearch(ar,18); // 出力：8
8が3番目、18が8番目にあることを O(log N) 時間で探索できます。O(N) の線形探索とは比べ物にならないほど速いですね。ただし、二分探索はソート済みの配列にしかおこなえないので、注意が必要です。
この記述方法で配列内に存在しない値も探索することができますが、その場合は負の値が戻ってくるので、ビット反転の演算子 "~" を使って正の値にしてから受け取ります。このとき受け取る負の値は補数というみたいなんですが、正直よくわかっていません。
int[] ar = {2,4,6,8,10,12,14,16,18,20}; int a = ~Arrays.binarySearch(ar, 9); // 出力：4 int b = ~Arrays.binarySearch(ar,15); // 出力：7
さて、そんな二分探索にも欠点が一つあります。配列内に同じ要素が複数個含まれていて、その同じ要素を探索する場合に、戻り値が一定でなくなってしまうのです。例えば、以下のような配列です。
int[] ar = {1,1,1,1,2,2,2,2}; int a = Arrays.binarySearch(ar, 1); // 出力：3 int b = Arrays.binarySearch(ar,2); // 出力：5
1のほうは前から4番目のものが戻り値となっていますが、3のほうは前から2番目のものが戻り値となっています。このような戻り値で問題なければそれでいいのですが、同じ要素が複数あるときにはそのうちの先頭、あるいは末尾の位置を受け取りたい場合もあります。そんなときに便利なのが LowerBound, UpperBound の二分探索です。
LowerBound の二分探索では、「指定した値以上の要素」が初めて出現した位置が戻り値になります。
Integer[] ar = {1,1,1,1,2,2,2,2};
int a = ~Arrays.binarySearch(ar, 1, (x,y)->x.compareTo(y)>=0?1:-1);
// 出力：0
Comparator を使うのが関係しているのか、Integer などのオブジェクト型の配列しか扱えないみたいです。出力を見ると、1以上の値が初めて出現する位置なので、戻り値は0となっています。
次に UpperBound の二分探索です。こちらは、「指定した値より大きい要素」が初めて出現した位置が戻り値になります。
Integer[] ar = {1,1,1,1,2,2,2,2};
int a = ~Arrays.binarySearch(ar, 1, (x,y)->x.compareTo(y)>0?1:-1);
// 出力：4
比較演算子が >= から > になっただけの違いですね。なお、LowerBound, UpperBound の二分探索では戻り値が全て負の値になるので、正の値として使いたいならビット反転は必須です。
ここまで記事を読んでくださって、二分探索を試してみたくなった方は、ぜひ以下の問題を解いてみてください。
LowerBound, UpperBound の二分探索を組み合わせると、うまく解くことができます。
