二分的本质是划分两个区间，使得满足某种条件处于左left区间，满足另外一种条件的处于right区间。

有单调性的题目一定可以二分， 可以二分的题目不一定非要有单调性(可以先sort构造出单调性)

更新l, r的思路: 每次更新区间l,r时，都要保证target在区间内

• 因为arr[mid] < / <=target ，所以 target必定在mid ~ r之间，因此更新l；
• 因为arr[mid] > / >= target，所以 target必定在l ~ mid之间，因此更新r.

整数二分

相错终止模板

要领：

• l 与 r是数组的左右闭区间 ，即 l = 0且r = arr.size() - 1
• while()括号内的条件: while (l <= r)或while (l != r + 1)
• arr[mid]与tar，或者说是check(mid)函数:
  • check(mid)函数该怎么写，并对应更新区间的哪个端点

..., idx_upper] target [idx_lower, ...

其中 : idx_upper = l - 1（r）; idx_lower = r + 1（l） 。

以$lower \_ bound$举例:

• 循环结束后一定满足: l == r + 1

---

lower_bound模板

lower_bound(以target为下界: target [lower, ...返回第一个[插入target后，arr仍然保持有序]的下标

#include <vector>
#include <iostream>

using namespace std;

int binary_search1(vector<int> &arr, int target) {
    int l = 0, r = arr.size() - 1;
    
    while (l != r + 1) {
        int mid = l + (r - l) / 2;
        if (arr[mid] >= target) {
            // r的右边(不包括r)全大于等于target
            r = mid - 1;
        } else {
            // l的左边(不包括l)全小于target
            l = mid + 1;
        }
    } 
    
    return l; // return r + 1; // lower_bound
}

应用: 在数组arr中找到大于等于target的最小值

• 使用binary_search1():

#include <vector>
#include <algorithm>   // sort()

using namespace std;

vector<int> arr;
sort(arr.begin(), arr.end());
int idx_lower = binary_search1(arr, target);
int lower = idx_lower == arr.size() ? -1 : arr[idx_lower];

• 使用lower_bound()函数达到相同目的:

C++: lower_bound函数(Defined in header <algorithm>)

返回第一个大于等于target的下标迭代器

#include <vector>
#include <algorithm>   // sort() & lower_bound() & upper_bound

using namespace std;

vector<int> arr;
sort(arr.begin(), arr.end());
auto it_lower = lower_bound(arr.begin(), arr.end(), target);
// int idx_lower = it_lower - arr.begin(); // 下标可以求但没必要
int lower = it_lower == arr.end() ? -1 : *it_lower;

---

upper_bound模板

upper_bound(以target为上界: ... upper] target) 返回最后一个[插入target后，arr仍然保持有序]的下标

#include <vector>
#include <iostream>

using namespace std;

int binary_search2(vector<int> &arr, int target) {
    int l = 0, r = arr.size() - 1;
    
    while (l != r + 1) {
        int mid = l + (r - l) / 2;
        if (arr[mid] <= target) {
            // l的左边(不包括l)全小于等于target
            l = mid + 1;
        } else {
            // r的右边(不包括r)全大于target
            r = mid - 1;
        }
    } 
    
    return r; // return l - 1;
    // return l;    // upper_bound
}

应用: 在数组arr中找到小于等于target的最大值

• 使用binary_search2():

#include <vector>
#include <algorithm>   // sort()

using namespace std;

vector<int> arr;
sort(arr.begin(),arr.end());
int idx_upper = binary_search2(arr, target);
int upper = idx_upper() == -1 ? -1 : arr[idx_upper];

• 使用upper_bound()函数达到相同目的:

C++: upper_bound函数(Defined in header <algorithm>)

$upper\_bound()$返回第一个大于target的下标迭代器，那么小于等于就是prev(it)

#include <vector>
#include <algorithm>   // sort() & lower_bound() & upper_bound

using namespace std;

vector<int> arr;
sort(arr.begin(), arr.end());
auto it_upper = upper_bound(arr.begin(), arr.end(), target);
// int idx_upper = it_upper - arr.begin(); // 下标可以求但没必要
int upper = it_upper == arr.begin() ? -1 : *prev(it_upper);  // 注意这里是it_upper的前一个迭代器**练习eg:**

练习eg:

Acwing-789.数的范围

---

二分答案

二分答案用于解决诸如"最大值最小、 最小值最大"等最优化问题。

思想：由于问题具有单调性，就能把一个最优化问题转化为判断是否可行问题
做法：分析题目答案的值域范围，二分答案值域， 然后check(mid)是否在定义域内(是否可行)，一步步收缩值域两端l、r，最终得到答案(分界点)。

check(mid)实际上就是0-1可行性函数，要在这个函数上二分查找分界点：

• 至少<=>要使得最大值最小<=>check(mid)可行时收缩右区间<=>$lower\_bound$

• 至多<=>要使得最小值最大<=>check(mid)可行时收缩左区间<=>$upper\_bound$

#include <algorithm>

// check函数可以用lambda匿名函数写
auto check = [&](int x) -> bool {
    if (/* 满足题目条件 */) return true;
    else return false;
}

// 假设值域范围为闭区间[left, right]
int l = left, r = right;
while (l != r + 1) {
    int mid = l + (r - l) / 2;
    if (check(mid)) {
        l = mid + 1;
    }
    else {
        r = mid - 1;
    }
}

return r;

练习eg:

Acwing-102.最佳牛围栏

浮点数二分

浮点数二分， 由于/号不会有向下取整的问题， 因此不需要考虑边界问题

要领：

• l 与 r同样是数组的左右闭区间
• while() 括号内是 r - l > 题给精度1e5
• 只有一种模板，return l 还是 return r都一样

#include <iostream>

using namespace std;

int main() {
    double x;
    cin >> x;

    double l = 0, r = x;
    while (r - l > 1e-6) {
        double mid = l + (r - l) / 2; // 浮点数二分 /号不会有向下取整的问题
        // eg:找几何平均数
        if (mid * mid >= x) {
            r = mid;
        }
        else {
            l = mid;
        }
    }
    return l; //return r也可以    
}

练习eg:

Acwing-790.数的三次方根