在非线性搜索的情况下在非常大的数组中找到比给定数字更小的数字

Question

我想查找小于或等于给定数字的最后一个数字。由于整数向量非常大，O（n）效率不高。

我将矢量分成两部分并进行平行搜索。

让我们用一个例子了解： -

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的任何位置，所以我们仍然必须完全搜索第二个数组，因为我们的目标是找到最大索引处的元素。

我想问是否有任何stl函数在第二个数组中找到小于2的数字，以便我没有完全搜索第二个数组。

我可以使用std :: find在第二个数组中找到一个小于2的数字吗？

编辑：小于或等于2的数字位于位置5（索引4），但它可能位于大于5的任何位置，因此我们停止在第一个数组中的位置5，但继续搜索第二个数组。假设我们得到位置7（索引6）的元素1，因为7> 5，所以我们返回位置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"; 
    } 
}