Kotlin で一般化した二分探索（めぐる式二分探索）

Kotlin 標準ライブラリの binarySearch が競技プログラミング用には微妙に使いづらいので自作した。

参考: 二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜

コピペ用

fun myBinarySearch(begin: Int, end: Int, isOk: (key: Int) -> Boolean): Int {
  var ng = begin
  var ok = end

  while (Math.abs(ok - ng) > 1) {
    val mid = (ok + ng) / 2
    if (isOk(mid)) {
      ok = mid
    } else {
      ng = mid
    }
  }

  return ok
}

fun <T> List<T>.myBinarySearch(isOk: (T) -> Boolean): Int {
  return myBinarySearch(-1, size) { index -> isOk(get(index)) }
}

fun <T> Array<T>.myBinarySearch(isOk: (T) -> Boolean): Int {
  return myBinarySearch(-1, size) { index -> isOk(get(index)) }
}

使い方

// 一般化した二分探索の例
myBinarySearch(0, 100) { it * it > 50 } // -> 8

// 逆からも探索可能
myBinarySearch(100, 0) { it * it < 50 } // -> 7

// List の拡張関数として使う例 （Array も同様）
val list = listOf(2, 4, 6, 8, 10)
list.myBinarySearch { it >= 5 } // -> 2

備考

• Kotlin 標準ライブラリの binarySearch は何が使いづらいのか？
  • 等しい要素が複数存在する場合どれを返すかが不定（lower_bound 的な事ができない）
  • List や Array の拡張関数として実装されているので、一般化した二分探索に使えない
    • ex: 年齢当てゲーム
• 関数名が binarySearch ではない理由
  • List 等の拡張関数として実装しようとした際にシャドーイングされるからです…
  • IntelliJ とか IDE の補完で余計な候補を出さないようにする効果もある（わりと大事）
• AtCoder での実装例（ABC077 C - Snuke Festival）
  • 一般化した二分探索を使った回答 提出 #13412420
  • List の拡張関数として二分探索を使った回答 提出 #13412486