【C++】lower_bound 和 upper_bound

lower_bound:在已排序好的陣列中,回傳第一個「大於或等於」指定值的位置。
upper_bound:改成「大於」。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    vector<int> v = {1, 3, 3, 5, 7, 9};
    sort(v.begin(), v.end());
    auto it = lower_bound(v.begin(), v.end(), 3);
    if(it != v.end()){
        cout << "v[" << (it - v.begin()) << "] = " << *it;
    }
}
v[1] = 3 // lower_bound
v[3] = 5 // upper_bound

時間複雜度:O(log n)。(二分搜尋法)

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *