STL 的內建二分搜

如何方便的把二分搜應用在 STL 上

二分搜的各種邊界問題很容易賽中寫爛，有些時候甚至還要配合特定的資料結構，如果總是手刻會有些麻煩， 因此 STL 提供了內建的二分搜可以用，需要 #include <algorithm> ，複雜度根據資料結構的特性決定。

使用條件

首先，要求這個資料是排序好的，預設要求遞增，但可以用參數變成倒序。傳入的範圍一律是左閉右開。

再來，結構本身需要提供迭代器，因為 STL 中的函式是透過迭代器實作的。

如果他是一個可以隨機存取(vector, array(含 C++11 後的 STL array 和內建的陣列))，便可以 $O(1)$ 得到區間長度、 $O(1)$ 存取中間那一項，總共做 $\log n$次，因此總複雜度是 $O(\log n)$ 。

而如果是樹形結構((multi)set, (multi)map)，直接用 <algorithm> 中的函式會使複雜度到 $O(n+\log n)$ ，要使用他們兩個自己的成員函式，才能保證總複雜度是 $O(\log n)$

除了上面兩種複雜度是好的以外，剩下的結構如果需要 $O(n)$ 才能找到區間長度，或者要花 $O(n)$ 才能找到 $n$ 項後的迭代器，就會造成總複雜度是 $O(n\log n)$ 的，如 list, unordered_(multi)set, unordered_(multi)map, string。

至於那些沒有迭代器的結構(通常是存取後面的資料會有副作用，需要移除一些元素)，則無法使用，如 stack, queue, deque, priority_queue。

用法

有三個版本 binary_search 回傳一個 bool ，表示是否有這個值。

其餘兩個回傳地址(對大部分資料結構來說，相當於一個迭代器)，若沒有符合範圍的答案，一律回傳傳入的右界。

lower_bound 是回傳大於(或小於)等於要尋找的數字中，最小值的位置。

upper_bound 是回傳大於(或小於)要尋找的數字中，最小值的位置。

(這也是左閉右開的原因，判斷是右界就可以知道沒有符合的答案。)

第一個參數是左界，第二個是右界，第三個是要判斷的值。

第四個是可選的，傳入一個比較函式，用自訂的方式尋找答案。

而 set 和 map 自己的成員函式則不包含前兩個參數，其餘部分相同。

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
int main() {
    int n, x;
    cin >> n >> x;//假設傳入4 2
    
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        v[i] = i;//裡面是0 1 2 3
    }
    int a[n];
    for (int i = 0; i < n; ++i) {
        a[i]=n-i-1;//裡面是3 2 1 0
    }
    cout << *lower_bound(v.begin(), v.end(), x) << '\n';//回傳v[2]，也就是2所在的位置
    cout << binary_search(a, a + n, x, greater<int>()) << '\n';//第四個參數是內建函式，可以遞減搜尋，回傳true，因為2有在a裡
    
    set<int> s(v.begin(),v.end());
    map<int, string> m = {{0, "冰川好電"}, {1, "winliu好勝利"}, {2, "rickytsung跟我貼貼"}, {3, "沒寫到的對不起，我懶得打了w"}};
    
    cout << *s.lower_bound(x) << '\n';//回傳2所在的位置
    cout << m.upper_bound(x) -> second << '\n';//回傳{3,"沒寫到的對不起，我懶得打了w"}所在的位置
    
    multiset<int>ms = {-1, 0, 0, 1};
    multimap<char,int>mm = {{'a', 1}, {'c', 2}, {'c', 3}, {'d', 4}};
    
    cout << (ms.lower_bound(x) == ms.end()) << '\n';//找不到，因此回傳 ms.end()
    cout << mm.upper_bound('a' + x) -> second << '\n';//回傳{'d', 4}所在的位置
    
    return 0;
}