lower_bound (最初に >= target の位置)

並び替え済みの配列で、目当ての値以上の数が最初に現れる位置を返します。値そのものを探すのではなく、値が切り替わる境目を探す。ここがこれまでとの違いです。

同じ値が並んでいると、どれが返るか分からない

[1, 3, 5, 5, 7, 9] から 5 を探す場面を考えます。5 は 2 番目と 3 番目の 2 か所にあります。真ん中から見ていって、たまたま 3 番目の 5 に当たったら、そこで答えを返してしまう。これが値そのものを探す書き方の限界です。

どちらも 5 なので間違いとは言い切れませんが、「何個あるか」「どこから始まるか」を知りたいときには使えません。ほしいのは必ず先頭の 5 の位置です。

探すのは値ではなく、境目

見方を変えます。配列を、目当ての値より小さい区画と、それ以上の区画の 2 つに分けて考えます。

並び替え済みなら、この 2 つの区画は必ず左右にきれいに分かれます。途中で入り混じることはありません。だから真ん中を 1 か所見れば、そこが小さい側か以上側かが分かり、境目がどちらにあるかも決まります。半分を捨てられる根拠は、値が一致するかどうかではなく、この分かれ方のほうにあります。

見つかっても、まだ止まらない

ここが今回いちばんの勘所です。真ん中の値が目当ての値とぴったり一致しても、そこで返してはいけません。その左にもう一つ同じ値が隠れているかもしれないからです。

一致したときに分かるのは「境目はここか、ここより左」ということだけです。範囲を左側に詰めて、続きを見ます。範囲が 1 点に潰れたところが、探していた境目になります。

値を探す書き方が見つけたら即終了だったのに対して、境目を探す書き方は最後まで詰めきってから答える形になります。前回まで身につけた「見つけた瞬間に抜ける」を、ここでは意識して封じることになります。

このぶん、範囲の詰め方も変わります。一致した位置は答えかもしれないので、次の範囲から外してはいけません。真ん中を捨てながら進む書き方をそのまま持ち込むと、正解の位置を落として 1 つずれた答えが返ります。

無いときは、末尾の 1 つ先

目当ての値以上の数が 1 つも無い場合は、配列の長さをそのまま返します。存在しない位置ですが、これには意味があります。並び順を保ったままその値を差し込むなら、ちょうどそこに入れればよい、という位置だからです。

そう決めておくと、見つからなかったことと、末尾に足せばよいことを同じ数値で表せます。前回までの -1 のような特別扱いが要らなくなる、というのがこの仕様の狙いです。

逆側から見ると、すべての要素が目当ての値以上のときは 0 が返ります。この場合も「先頭に差し込めばよい位置」として読めます。返ってくる数値は必ず 0 から配列の長さまでの範囲に収まり、そのどれもが差し込み位置として意味を持ちます。無効な値がひとつも無いので、呼ぶ側で場合分けを書かずに済みます。

1. 二分探索 (O(log n)) で実装する
2. 見つからない場合は配列長 n を返す
3. 重複がある場合は最初の位置を返す