めぐる式lower_bound, upper_bound in Ruby
今日のランチタイム、Rubyにlower_bound
とupper_bound
がないことに気づいた。
二分探索だとArray#bsearch
はあるみたいだけど、これは値を返してしまうから情報量が少ない。C++にあるstd::lower_bound()
とstd::upper_bound()
が欲しい。
ということで、めぐる式にぶたんの考え方に則ってそれぞれ書いてみた。
lower_bound
: 探索したい値以上の値が最初に現れる位置を返す
def lower_bound(arr, n)
ng = -1
ok = arr.size
while (ok - ng).abs > 1
mid = (ok + ng) / 2
if n <= arr[mid]
ok = mid
else
ng = mid
end
end
ok
end
upper_bound
: : 探索したい値より大きい値が最初に現れる位置を返す
def upper_bound(arr, n)
ng = -1
ok = arr.size
while (ok - ng).abs > 1
mid = (ok + ng) / 2
if n < arr[mid]
ok = mid
else
ng = mid
end
end
ok
end
※めぐる式というのはバグりづらい二分探索の実装パターンのことです。
※詳しくは:https://twitter.com/meguru_comp/status/697008509376835584
おわかりの通り、普通に二分探索するものです。
「なんで2種類あるの?」「これが何の役に立つの?」というもっともな疑問が立ち上がってくるわけですが、
例えばこんな配列があったとき(当然ソート済みとして)
arr = [1, 1, 2, 2, 2, 3, 3]
このとき、
lower_bound(arr, 2) #=> 2
つまり、2以上の要素が最初に現れるインデックスが2
であることがわかりました(実際そうなってますね)。
ということは、これより小さいインデックスの要素は全て2
より小さいことがわかります。逆にこれより大きいインデックスの要素は全て2
以上です(それはそう)。
ということで、インデックスがわかることによって、「n以上の要素の個数」とか「nより小さい要素の個数」みたいなことががわかります。
upper_bound(arr, 2) #=> 5
つまり、2より大きい要素が最初に現れるインデックスが5
であることがわかりました(この場合、要素の値は3)。
こちらも同様に、インデックスがわかることによって要素の個数などが求められたりして便利です。
ここで例えば、2
以下の要素の個数が知りたいよってとき、lower_bound(arr, 3)
とすれば値3
が最初に現れるインデックスがわかるわけなので、
それを-1
すれば個数がわかるじゃんupper_bound
いらないじゃんとなりそうですが、
でもそれは配列の中で2
の次に大きい要素が3
とこの場合わかっているからであり、どんな要素が入っている配列かわからない場合はupper_bound(ary, 2)
として「2
より大きい値が最初に現れる位置」を求める必要があるのでやっぱりupper_bound
が必要です。
さらにこの2つを組み合わせると、
lower_bound(arr, 2) #=> 2 (2以上の要素が最初に現れるインデックス)
upper_bound(arr, 2) #=> 5 (2より大きい要素が最初に現れるインデックス)
こうなり、ここから「要素2
が連続する区間」がわかります。てことは個数もわかります。これは便利!!1
しかも二分探索なので速い!当たり前!以上!
おまけ(雑)
二分探索とは、探索対象のサイズがステップごとに半分になっていくやつ。
時間計算量$$O(\log N)$$。
でもどうして$$O(\log N)$$なの?$$\log N$$?は?と誰しも一度は思ったことがあると思うのでおさらい。
要素数32の配列の中からある値を見つけるとき、二分探索だと極端に言えばこんな感じに探索対象が減っていく。
32(全部) -> 16 -> 8 -> 4 -> 2 -> 1(特定)
という感で最初は32個あった探索対象が1/2で絞られていって最後は1つに特定される。
逆の言い方をすれば
1(特定) -> 2-> 4 -> 8 -> 16 -> 32(全部)
という風に$$2^{ステップ数}$$で元の要素数になる。
つまり、要素数Nの配列があるとき
$$2 ^ {ステップ数} = N(元の要素数)$$ となる。
よって両辺にlogをとると、$$ステップ数 = \log N$$ (Nは要素数)。
※対数の底は無視(底の変換するだけ = 定数倍の差なので)