std::lower_bound と std::upper_bound の根拠は？

質問

STLには2値探索関数 std::lower_bound と std::upper_bound があります。 しかし、私はそれらを使用しない傾向があります。なぜなら、それらが何をするのか思い出せないからです。 なぜなら、それらの契約は私にとって完全に不可解に思えるからです。

名前を見ただけでは "lower_bound" は "last lower bound" の略ではないかと推測しています。

すなわち、ソートされたリストの中で、与えられた値 (もしあれば) と <= している最後の要素です。

そして同様に、私は "upper_bound" が "first upper bound" の略ではないかと推測しています。

すなわち、ソートされたリストの中で、与えられた値（もしあれば）である >= の最初の要素です。

しかし、ドキュメントによると、それとはかなり異なることをするようです。 私には、後ろ向きとランダムが混在しているように見えます。 ドキュメントを言い換えると、以下のようになります。

- lower_boundは、>= valである最初の要素を見つけます。

- upper_boundは、> valである最初の要素を見つけます。

ということは、lower_boundは下限を見つけることはなく、最初の 上 を見つけるのです。 そして upper_bound は最初の 厳密な上限 の境界を見つけます。

これは何か意味があるのでしょうか？ どうやって覚えているのですか？

どのように解決するのですか？

範囲内に複数の要素がある場合、[ first , last ) と等しい値を持つ val と等しい値を持つ場合、その範囲 [ l , u ) ここで

l = std::lower_bound(first, last, val)
u = std::upper_bound(first, last, val)

に等しい要素の範囲が正確です。 val の範囲内で、[ first , last ). そこで l と u の下限と上限です。 等しい範囲 . 半開放の区間で考えるのに慣れていれば、これは理にかなっています。

(なお std::equal_range は一回の呼び出しで下限と上限の両方をペアで返すことに注意してください)。