メモ lower_bound, upper_bound

数値とかのソートされた配列aに対して

• lower_bound(a.begin(), a.end(), k) は aの中で ai≧k となる最小のポインタを求める。
• upper_bound(a.begin(), a.end(), k) は aの中で ai>k となる最小のポインタを求める。

これらを使ってaの中の値がkの要素の数は

upper_bound(a.begin(), a.end(), k) - lower_bound(a.begin(), a.end(), k)

と書けるし、

その要素自体は

*upper_bound(a.begin(), a.end(), k)

で参照できる。

aのソートの向きによる違いは後で調べておく。