在非線性搜索的情況下在非常大的數組中找到比給定數字更小的數字

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"; 
    } 
}