今日のランチタイム、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が連続する区間」がわかります。てことは個数もわかります。これは便利！！１
しかも二分探索なので速い！当たり前！以上！

おまけ（雑）

二分探索とは、探索対象のサイズがステップごとに半分になっていくやつ。
時間計算量$$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は要素数)。

※対数の底は無視（底の変換するだけ = 定数倍の差なので）