C++常用二分库函数

容器相关二分

在有序容器中找第一个大于或大于等于指定元素的迭代器

第一个大于：upper_bound

第一个大于等于：lower_bound

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> arr = {1, 6, 9, 10, 15, 16, 20, 23, 55, 78, 98, 100};
    auto it = upper_bound(arr.begin(), arr.end(), 8);
    cout << distance(arr.begin(), it) << ": " << *it << endl;
    it = upper_bound(arr.begin(), arr.end(), 23);
    cout << distance(arr.begin(), it) << ": " << *it << endl;
    it = lower_bound(arr.begin(), arr.end(), 23);
    cout << distance(arr.begin(), it) << ": " << *it << endl;
}

输出

2: 9
8: 55
7: 23

同时找第一个大于和大于等于的元素

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> arr = {1, 6, 9, 10, 15, 16, 20, 23, 55, 78, 98, 100};
    auto p = equal_range(arr.begin(), arr.end(), 55);
    cout << distance(arr.begin(), p.first) << " " << distance(arr.begin(), p.second);
}

输出

8 9

在容器中找最大值和最小值

二分查找：max_element, min_element, 返回的是对应元素的指针

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> arr = {1, 6, 9, 15, 10, 16, 120, 23, 89, 78, 98, 100};
    auto mmax = *max_element(arr.begin(), arr.end()), mmin = *min_element(arr.begin(), arr.end());
    cout << mmax << " " << mmin << endl;
}

输出

100 1

在有序容器中插入新元素保证有序

结合upper_bound和vector的insert方法

#include <bits/stdc++.h>
using namespace std;

void print(const vector<int>& vec) {
    for (const auto n : vec) {
        cout << n << " ";
    }
}

int main() {
    vector<int> arr = {1, 6, 9, 10, 15, 16, 20, 23, 55, 78, 98, 100};
    // 插入50，原始数组升序，因此获得第一个大于50的元素位置，插在那里
    auto pos = upper_bound(arr.begin(), arr.end(), 50);
    arr.insert(pos, 50);
    print(arr);
}

输出

1 6 9 10 15 16 20 23 50 55 78 98 100 

查询是否有指定元素

binary_search

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> arr = {1, 6, 9, 10, 15, 16, 20, 23, 55, 78, 98, 100};
    cout << binary_search(arr.begin(), arr.end(), 23) << endl;
    cout << binary_search(arr.begin(), arr.end(), 21) << endl;
}

注：binary_search的复杂度是$O(\log(n))$, 而通用的find是$O(n)$的，且binary_search要求容器必须是有序的

二分库的自定义比较函数

自定义比较函数用于告诉编译器该有序数组是按照何种规则有序的，默认就是<

比如若stl容器存储的非基本类型而是类，容器按照类的某个属性有序排列，那就要在比较函数中告诉编译器按照该属性的比较规则（<升序，>降序）