lower_boundとupper_bound、ややこしい仕様ではあるのだけれども …

---

32.6.1    ２分探索

…(略)…

lower_bound(first,last,k)は、kを探索するのではなく、kより大きなキーをもつ先頭の要素を指す反復子を返す。ただし、kより大きなキーをもつ要素が存在しなければlastを返す。同様のエラー通知方法は、upper_bound()やequal_range()でも行われている。

---

原文：

If lower_bound(first,last,k) doesn’t find k, it returns an iterator to the first element with a key greater than k, or last if no such greater element exists. This way of reporting failure is also used by upper_bound() and equal_range().

---

試訳：

lower_bound(first,last,k)がkと一致するキーを見つけられない場合はkより大きなキーを持つ最初の要素を指す反復子を、その様な要素が存在しない場合はlastを返す。同様のエラー通知方法は、upper_bound() と equal_range() でも用いられている。

---

考察：

ややこしいが、（探索に成功した場合）lower_boundはkと一致する最初の要素を返し、upper_boundはkより大きなキーを持つ最初の要素を返す。なので「kを探索するのではなく」だとupper_boundの仕様になってしまう。たぶん、一覧表の方に出ているlower_bound関数の仕様（p=lower_bound(b,e,v)  pは、[b:e)内で最初に出現するvを指すようになる）を忘れていて、かつ文頭の”If”を見落としている。