引言
二分也就是二分查找，又叫折半查找。这种算法正如其名，每一次都要分一半。
二分算法可以分为二分查找和二分答案。
以在一个升序数组中查找一个数为例，每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找
二分法的使用条件
二分法是适用于解决具有“二段性”(单调性)的问题的方法，通常表现为求解满足某一条件的最大值或者最小值
- 上下界确定。 我们可以通过上下界的折半来优化查找。
- 二段性： 对某一范围内的数据，存在一个临界点，使得临界点某一侧的所有数据都满足某一性质，另一侧的所有数据都不满足这一性质，就称这一范围内的数据具有二段性。
二段性包括单调性，即区间内有序，这样二分出来的结果是严格大于或者小于或等于target的。
但是，二段性也体现在非单调性上，也称为局部有序，可以参考 162. 寻找峰值 和 33. 搜索旋转排序数组。由这些题我们可以得知，二分法的奥义（本质）不在于单调性，而是二段性。也就是我们能对整体无序但局部有序的序列进行二分法。
二分的前提条件
1、答案在一个区间内（一般情况下，区间会很大，暴力超时）
2、直接搜索不好搜，但是容易判断一个答案可行不可行
3、该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。
4、若有多个答案满足题意，则这些答案具有如下特点：若答案 x 满足，则答案范围内小于 x 或大于 x 的答案均满足。
模板
🥑1 朴素版
while (l <= r)
{
int mid = (r - l) / 2 + l; //防止溢出,和mid = (r - l + 1) / 2 + l;等价
if (...) l = mid + 1;
else if (...) r = mid - 1;
else return ...;
}🍉2 求大于等于目标的最小值（查找区间左端点）
while (l < r) //区间不为空
{
int mid = ((r - l) >> 1) + l;
if (...) l = mid + 1;
else r = mid;
}🥝3 求小于等于目标的最大值（查找区间右端点）
while (l < r)
{// 当l,r相邻时，会l=mid,<r,死循环，模板1不影响，因为l=mid+1=r
int mid = ((r - l + 1) >> 1) + l;
if (...) l = mid;
else r = mid - 1;在朋友提醒下，找到了一个更好更实用的板子，如下：
// 左边界
int l = 0, r = n - 1;
int begin = 0, r = 0;
while(l <= r)
{
int mid = (r + 1) >> 1;
if(check1(mid)){
r = mid - 1;
begin = mid;
}
else l = mid + 1;
}
// 右边界
l = 0, r = n - 1;
while(l <= r){
int mid = (r + 1) >> 1;
if(check2(mid)){
l = mid + 1;
end = mid;
}
else r = mid - 1;
}
if(!check(begin)) begin = -1;
if(!check(begin)) end = -1;
return {begin, end};- 这个时候就不用考虑 Mid +1 右边界啥的问题了
例题
1. 二分查找
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r)
{
//int mid = (r - l) / 2 + l; //朴素版本下 两个都行
int mid = (r - l + 1) / 2 + l;
if (nums[mid] == target) return mid;
else if (nums[mid] > target) r = mid - 1;
else l = mid + 1;
}
return -1;
}
};
2. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target)
{
if (nums.size() == 0) return { -1,-1 };
int begin = 0;
// 1. 二分左端点
int l = 0, r = nums.size() - 1;
while (l < r) //区间不为空
{
int mid = ((r - l) >> 1) + l;
if (nums[mid] < target)l = mid + 1;
else r = mid;
}
// 判断是否有结果
if (nums[l] != target) return { -1,-1 };
else begin = l; //标记左端点
l = 0, r = nums.size() - 1;
while (l < r) //区间不为空
{
int mid = ((r - l + 1) >> 1) + l;
if (nums[mid] > target) r = mid - 1;
else l = mid;
}
return { begin, r};
}
};
用新的板子编写代码，如下：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target)
{
if (nums.size() == 0) return { -1,-1 };
int begin = 0, end = 0;
// 1. 二分左端点
int l = 0, r = nums.size() - 1;
while (l <= r) //区间不为空
{
int mid = (r + l) >> 1;
if (nums[mid] >= target){
r = mid - 1;
begin = mid;
}
else l = mid + 1;
}
l = 0, r = nums.size() - 1;
while (l <= r) //区间不为空
{
int mid = (r + l) >> 1;
if (nums[mid] <= target) {
l = mid + 1;
end = mid;
}
else r = mid - 1;
}
if(nums[begin] != target) begin = -1;
if(nums[end] != target) end = -1;
return { begin, end};
}
};
3. x 的平方根
class Solution {
public:
int mySqrt(int x) {
if (x < 1) return 0;
int l = 1, r = x;
while (l < r) //精度保证
{
long long mid = (r - l + 1) / 2 + l; //防止溢出
if (mid * mid <= x) l = mid;
else r = mid - 1;
}
return l;
}
};4. 搜索插入位置
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size();
while (l < r)
{
int mid = (r - l) / 2 + l;
if (nums[mid] < target) l = mid + 1;
else r = mid;
}
return l;
}
};5. 山脉数组的峰顶索引
思路：
该题仍具有二段性，左边递增，右边递减，用二分查找算法，
当前山峰高于左边山峰，区间往右缩小，否则往左缩小
注：封顶的左边区间，一定是递增的，因此套用模板三即可，找最右端点
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int l = 1, r = arr.size() - 2;
while (l < r)
{
int mid = l + (r - l + 1) / 2;
if (arr[mid] > arr[mid - 1]) l = mid;
else r = mid - 1;
}
return r;
}
};6、寻找峰值
思路：
该题相比于上题，该题有多个峰值存在，故在两个封顶之间的区间内，从左到右一定递增，故套用模板二，找区间左端点即可。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) // 左边如果不大于右边，则
{
int mid = (r - l) / 2 + l;
if (nums[mid] > nums[mid + 1]) r = mid ;
else l = mid + 1;
}
return l;
}
};7. 寻找旋转排序数组中的最小值
思路：
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
int x = nums[r];
while (l < r)
{
int mid = (r - l) / 2 + l;
if (nums[mid] <= x) r = mid;
else l = mid + 1;
}
return nums[l];
}
};8. 点名
思路：
按照缺失的数分为左右两个区间。
左边，nums[i] == i (left = i + 1)
右边 nums[i] > i. (right = i)
注：当缺失的数是最后一个数，需要做下特殊判断，因此r 从 n 开始
class Solution {
public:
int takeAttendance(vector<int>& records) {
int l = 0, r = records.size();
while (l < r)
{
int mid = (r - l) / 2 + l;
if (records[mid] == mid) l = mid + 1;
else r = mid;
}
return l;
}
};9. A-B 数对
思路：
这里使用库函数二分的写法：
依次枚举 A ，将问题转变成统计数列中 B + C 出现了多少次。先对数列排序，那么 B + C 会对应这个数列的连续一段，只要找到这个连续段的左端点和右端点即可。(需使用头文件 algorithm)
- lower_bound(begin, end, val)在区间 [begin, end)中找到val第一次出现位置；
- upper_bound(begin, end, val)在区间 [begin, end)中找到val最后一次出现位置的后面一位
则这个数出现的次数就可以表示为 upper_bound() - lower_bound()，时间复杂度为 O(nlogn).
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int main()
{
int n, c;
cin >> n >> c;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
int tot = 0;
for (int i = 0; i < n; i++)
tot += upper_bound(a, a + n, a[i] + c) - lower_bound(a, a + n, a[i] + c);
cout << tot << endl;
return 0;
}
10. 进击的奶牛
思路：
先构造判断 “条件”：可以把 c 头牛全部安置进这些隔间使相邻两头牛距离不超过 x 。x 越小，就越可能把所有牛合法安置；当 x 比较大时，牛棚就不够安置了。于是，存在一个分界线 ans，当 x 大于 ans 时就没有合法的安置方案，当 x 小于或等于 ans 时，则一定存在一个合法的安置方案。
可以得到，在合法的答案中，任意两个相邻安置点都不能小于 x 。那么只需要遍历所有点，从最左端开始，每隔超过 x 的距离，能安置则安置，最后判断能否全部安置完。若不能，则缩小 x ，重复上述遍历过程。
#include <iostream>
#include <algorithm>
using namespace std;
int a[100005], n, m;
//注意：这是拿出来的那些里，mid为最短距离，和跳石头不同的是，跳石头是在留下的里面，mid为最短距离
bool check(int mid)
{
int now = 0, cnt = 0;
for (int i = 1; i < n; i++)
{
if (a[i] - a[now] >= mid) //计算有几个隔间距离大于mid
cnt++, now = i;
}
return cnt + 1 >= m; // + 1,是因为需要算上 a[1],//如果拿出的总个数大于等于m，都能保证拿走的瓶盖间距大于等于mid，那拿出来m个，肯定也能满足！！
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n); //排序隔间
int l = 1, r = a[n - 1] - a[0]; // 距离大于1
while (l < r)//找右端点
{
int mid = (r - l + 1) / 2 + l;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
return 0;
}
