整列済み配列への挿入位置を二分探索

2019-03-23
#algorithm

整列済みの配列に要素を追加するという処理がたびたび必要になるんだけど、二分探索で範囲を更新する際にどっちを+1/-1する必要があるのがわからないとか終了条件を間違えて無限ループするとかで毎回調べてたのでメモしておく。

用途

ライブラリなどで用意されているいわゆるbsearch関数では一致する要素がある場合にのみ結果が得られるが、挿入すべき位置を知りたいので一致する要素がない場合にも結果が欲しい。

コード

  • テストもしたのでちゃんと動くはず…。
  • codepenは実行結果のconsole出力を埋め込めないのね…。

境界条件

二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita で紹介されていた、めぐる式二分探索法だと+1しなくていいから間違えづらいとか：

function bsearchInsertPosition(array, value, compare = (a, b) => a < b) {
  let lo = -1, hi = array.length
  while (hi - lo > 1) {
    const m = lo + (((hi - lo) / 2) | 0)
    if (compare(array[m], value))
      lo = m
    else
      hi = m
  }
  return hi
}

function test(array, value, expect, compare) {
  const actual = bsearchInsertPosition(array, value, compare)
  if (actual !== expect) {
    console.error(`${value} in ${array}, expect=${expect}, actual=${actual}`)
  }
}

const array = [10, 20, 30, 40, 50]
test(array, 5, 0)
test(array, 20, 1)
test(array, 20, 2, (a, b) => a <= b)
test(array, 100, 5)

関連記事

新着記事