前提
基本的に競プロ（競技プログラミング）の文脈です。また、Kotlinで取り組んでいるのでKotlin固有の話も含まれるかもしれません。
めぐる式二分探索とは
こちらで紹介されている二分探索の実装テンプレートのことです。
このコードはたぶんC#で書かれていますが、Kotlinで書くとこんな感じになります。（他のを参考にしたので細かい部分は違います）
fun binarySearch(minNg: Int, maxOk: Int, isOk: (Int) -> Boolean): Int {
var ng = minNg
var ok = maxOk
while(abs(ok - ng) > 1) {
val mid = (ok + ng) / 2
if(isOk(mid)) {
ok = mid
} else {
ng = mid
}
}
return ok
}
めぐる式二分探索の使い方
たとえば以下のような数列があるとして
val list = listOf(1, 2, 3, 5, 5, 5, 7, 8, 9, 10)
その中から8が何番目にあるか知りたいとしたら、以下のように書きます。
val index = binarySearch(-1, list.size) { list[it] >= 8 }
println(index)
7
第1引数の minNg は探索の開始位置（含まない）、第2引数の maxOk は探索の終了位置（含まない）を指定します。
第3引数の関数は、探索したい値以上だったらtrueとなるようにします。二分探索を実行するにはある位置について比較結果がtrueならそれ以上は全部true、それより小さければ全部falseというような単調性が必要で、この isOk はその判定のために使うので、 list[it] == 8 のような条件にはしないということですね。
流れを追っていくとわかりますが、 isOk 以上となった要素は探索対象から除外して、ng となったほうの範囲に対して探索を続行します。 isOk がtrueの値を見つけたらただちに結果を返すのではなく、isOk がtrueとなる要素が ng の範囲にまだあるかどうかを調べるわけです。
この動きにより、探索対象の中で isOk を満たす値のうち最も左側の値が返ります。これはC++でいう lower_bound と同じ動きになります。
たとえば先程の数列には5が複数ありますが
val list = listOf(1, 2, 3, 5, 5, 5, 7, 8, 9, 10)
その中から5が何番目にあるかを指定してみますと
val index = binarySearch(-1, list.size) { list[it] >= 5 }
println(index)
このような実行結果となります。たしかに最も左側の値が返っています。
3
また、C++の lower_bound の対になる関数として upper_bound があります。対象の値より大きい値のうち最も左側にあるものを返すものですが、これは単純に対象の値 + 1で lower_bound すれば求められます。
なので5に対して upper_bound 相当の探索をしたい場合は
val list = listOf(1, 2, 3, 5, 5, 5, 7, 8, 9, 10)
このように指定すればいいです。
val index = binarySearch(-1, list.size) { list[it] >= 6 }
println(index)
6
つまり、めぐる式二分探索を使えば lower_bound も upper_bound もいけます。
KotlinのbinarySearchとの比較
そもそもめぐる式二分探索に興味を持ったのは、Kotlinの二分探索ライブラリではカバーできない範囲をカバーできるからということになります。
Kotlinの配列やListなどの各コレクション型には binarySearch メソッドを持っており、これを使えば二分探索ができます。
探索したい要素を直接指定し、それが存在する場合はその位置、存在しない場合は負の値が返るという仕様です。存在しない場合の負の値に1を足して符号を反転すると、探索対象が仮に存在していたらこの位置だったはず、という値になります。簡易的な lower_bound として使えます。
使い方がわかりやすいので便利なのですが、要素が複数ある場合はそのうちどれが返るかわからないという問題があります。lower_bound として使えるのは要素の重複がないことがわかっている場合のみです。
重複要素がある場合でも lower_bound や upper_bound を使いたいなあと思って自作しようかと思ったのですが、めぐる式二分探索があればどちらもいけるとわかって嬉しい、というのがこの記事でした。
なお binarySearch メソッドを使うことがなくなるかというともちろんそんなことはありません。競プロで使うことを想定すると、めぐる式二分探索の実装はいちいちコードをコピペしないと使えないので、 binarySearch メソッドで事足りるものは binarySearch メソッドを使います。
また、上記のめぐる式二分探索だと値がない場合は負の数が返るという動きはしません。（値がない場合は、仮にあった場合はこの位置のはずという正の値が返る）
なので単純に存在有無を確認したい場合などは binarySearch メソッドを使ったほうが便利です。うまく使い分けていきたいですね。