c++ - C++ - ソートされた std::vector 内の要素のインデックス

Question

私std::vectorはソートされていることを知っています。I を使用std::binary_searchすると、要素がベクトル内にあるかどうかをログ時間で確認できます。残念ながらstd::binary_search、成功した場合はベクター内の要素のインデックスを返しません (または、アクセスする方法がわかりません)。std::find要素へのイテレータを提供しますが、ベクトルがソートされているという事実を使用しないため、ログ時間ではなく線形時間で実行されます。独自のバイナリ検索アルゴリズムを簡単に実装できることはわかっていますが、標準でこれを行う方法があるかどうかを知りたいです。

Answer 1

std::lower_bound(O(log(N)) およびstd::distance(O(1) ランダム アクセス イテレータの場合) を使用できます。

auto lower = std::lower_bound(v.begin(), v.end(), val);
// check that value has been found
const bool found = lower != v.end() && *lower == val;

次に、どちらか

auto idx = std::distance(v.begin(), lower);

または単純な算術演算:

auto idx = lower - v.begin();

Answer 2

lower_bound() 関数を使用します。一般的に役立つようにするのは少しファンキーですが、必要な目的には役立ちます。

Answer 3

STL c++ で lower_bound を使用して、次のようなことを試すことができます。

// ベクトルを v とする

int func(){
     int position = lower_bound(v.begin(),v.end(),element_to_be_searched) - v.begin();
     if(position == v.size()) // element not found
     {
         return -1;
     }
     else{
          return position;
     }
}

Answer 4

std::binary_searchあなたが得ることができる微調整：

template<typename Iter, typename T>
Iter my_find(Iter begin, Iter end, T value)
{

    Iter i = std::lower_bound(begin, end, value);

    if (i != end && *i == value)
        return i; // found in container
    else
        return end; // not found
}

auto it = my_find(v.begin(), v.end(), val); //it is your iterator