1

ソートされたベクトル V で、c++ でバイナリ検索を実行したいと思います。特に、ベクトルのエントリの正確な値を見つけることに興味はありません。V[j-1] <= X < V[j] (X は入力値) を満たすエントリの位置 j を見つけたいと思います。

例: ベクトル v={1, 4, 7, 12, 17, 55} および X=8 の場合、関数は 3 を返す必要があります。

O(log(2)) の複雑さで STD 関数 binary_search を使用できますか?

そしてどうやって？

どうもありがとう、

アル。

4

3 に答える 3

4

Bartosz がリンクした機能に関するメモ:

  • upper_bound(begin, end, value)指定された値より大きい最初の要素を返します。これは、それを挿入して順序を維持できる間隔の終わり(または終わりの 1 つ後) です。
  • lower_bound(begin, end, value)指定された値以上の最初の要素を返します。これは、挿入できる間隔の始まりです

したがって、実際には：

std::vector<int> v = {1, 4, 7, 12, 17, 55};
int x = 8;
auto first = std::lower_bound(v.begin(), v.end(), x);
auto last = std::upper_bound(first, v.end(), x);

与えるべきfirst == last && *first == 12です。これは挿入できた半開区間[first,last)が空いているためです。x

これは通常、実際に要求したものよりも便利であることに注意してください。

std::vector::insert(iterator, value)

指定された反復子の前に挿入するため、upper_boundここの結果をいつでも使用できます。

于 2013-06-11T16:32:54.683 に答える
2

要件ごとに、使用する正しい STL 関数は upper_bound です。構文：

upper_bound(V.begin(),V.end(),val)-V.begin()

求める 0 ベースのインデックスを返します。

于 2013-06-11T16:33:34.637 に答える