c++ - log(n) 時間で、並べ替えられたベクター内の要素への反復子を取得します。

Question

ソートされたベクトルがあり、その中の特定の要素を見つけたいと思っています。これに使用できますbinary_searchが、存在するかどうかのみがわかります。要素にアクセスするための反復子も必要です。これには簡単な方法がありますか、それとも順番に検索する必要がありますか。

どんな助けでも感謝します。

Answer 1

lower_boundと を調べupper_boundます。lower_bound最初に一致する要素に反復子をupper_bound与え、最後に一致する要素の 1 つ後ろの反復子を与えます。

いずれかのアルゴリズムが一致を見つけられなかった場合、ソートされたコンテナを維持するためにアイテムを挿入できる場所にイテレータを返します。

binary_search誤解を招くような名前だといつも感じていました。