リニア検索なしの非常に大きな配列の中で与えられた数よりも小さい数を見つける

Question

与えられた数よりも小さいか等しい数の最後のオカレンスを見つけたい。整数ベクトルは非常に大きいので、O（n）はそれほど効率的ではありません。

私はベクトルを2つの部分に分割し、並列検索しました。

は一例と理解しましょう： -

vector <int> arr = {1, 8, 7, 1, 2, 9, 5, 7, 4 ,6}; 

私は2を言うために小さいか等しい数の最後の出現を見つけたいので、私は二つに配列を分割：

{1, 8, 7, 1, 2} and {9, 5, 7, 4, 6} 

と両方の配列の終わりから検索を開始しました。

私たちが見る通り、2より小さいか等しい数は位置5（インデックス4）にありますが、5より大きい任意の位置にあった可能性がありますので、2番目の配列全体を検索する必要があります。要素は最大インデックスになります。

2番目の配列に2より小さい番号を見つけるstl関数があるかどうかを尋ねたいので、2番目の配列を完全に検索しません。

2番目の配列で2より小さい数を見つけるためにstd :: findを使用できますか？

EDIT：2より小さいか等しい数は位置5（インデックス4）にありますが、5より大きい任意の位置にあった可能性があるので、最初の配列の位置5で停止しますが、2番目の配列の検索を続けます。 7> 5であるので、位置7（インデックス6）に要素1を取得したので、位置7を返してプログラムが終了するとします。これにより、最初の配列全体を検索する手間が省けました。

Answer 1

ベクトルから始めるので、最初から最後まで検索すればすべての要素を調べる必要があります。

ただし、最初から最後まで検索すると、述語が満たされるとすぐに停止できます。これは、アルゴリズムを最悪の場合のO（N）および最良の場合のO（1）にする。

#include <vector> 
#include <algorithm> 
#include <iostream> 


int main() 
{ 
    auto arr = std::vector <int>{ 1, 8, 7, 1, 2, 9, 5, 7, 4 ,6 }; 

    auto less_than_three = [](auto&& x) { return x < 3; }; 

    auto rpos = std::find_if(rbegin(arr), rend(arr), less_than_three); 

    if (rpos == rend(arr)) 
    { 
     std::cout << "not found\n"; 
    } 
    else 
    { 
     auto pos = prev(rpos.base()); 
     auto index = distance(begin(arr), pos); 
     std::cout << "found at position " << index << "\n"; 
    } 
}