Buer blog | 详情

二分法是什么

数学定义：二分法（Bisection method）即一分为二的方法. 设[a，b]为R的闭区间. 逐次二分法就是造出如下的区间序列([an，bn])：a0=a，b0=b，且对任一自然数n，[an+1，bn+1]或者等于[an，cn]，或者等于[cn，bn]，其中cn表示[an，bn]的中点。

典型算法：

算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。

基本思想：假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，

如果当前位置arr[k]值等于key，则查找成功；若key小于当前位置值arr[k]，则在数列的前半段中查找,arr[low,mid-1]；若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1,high]，直到找到为止。

二分法的使用条件

二分法是适用于解决具有“二段性”(单调性)的问题的方法，通常表现为求解满足某一条件的最大值或者最小值

`上下界确定。我们可以通过上下界的折半来优化查找。
二段性：对某一范围内的数据，存在一个临界点，使得临界点某一侧的所有数据都满足某一性质，另一侧的所有数据都不满足这一性质，就称这一范围内的数据具有二段性。
二段性包括单调性，即区间内有序，这样二分出来的结果是严格大于或者小于或等于target的。但是，二段性也体现在非单调性上，也称为局部有序，可以参考 162. 寻找峰值和 33. 搜索旋转排序数组。由这些题我们可以得知，二分法的奥义（本质）不在于单调性，而是二段性。也就是我们能对整体无序但局部有序的序列进行二分法。`

二分的前提条件

1、答案在一个区间内（一般情况下，区间会很大，暴力超时）
2、直接搜索不好搜，但是容易判断一个答案可行不可行
3、该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。
4、若有多个答案满足题意，则这些答案具有如下特点：若答案 x 满足，则答案范围内小于 x 或大于 x 的答案均满足。

算法模板：


//朴素版
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 ...;
}
			 
//求大于等于目标的最小值（查找区间左端点）
while (l < r) //区间不为空
{
    int mid = ((r - l) >> 1) + l;
    if (...) l = mid + 1;  
    else r = mid;
}
//求大于等于目标的最小值（查找区间左端点）			 
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;

案例大全

P1824 进击的奶牛

#include <bits/stdc++.h>
using namespace std; 
int v[100001];//根据 N 的范围开一个数组
int n, c, a;
bool check(int x) {
    int num = 0;//记录需要增加的牛栏数量
    int L = v[1];//第一头牛的位置
    for (int i = 2; i <= n; i++) {//枚举每一头奶牛的位置
        if (v[i] - L < x) num++;//如果当前奶牛的位置和第一头牛的位置的距离小于x
        else L = v[i];//否则 L更新为当前奶牛的位置
        if (num > a) return false;//如果需要增加的牛栏数大于满足当前状况的奶牛数量，直接 pass
    }
    return true;
}
int main()
{
    cin >> n >> c;//n 为总数  c 为不满足当前隔间分布的情况
    for (int i = 1; i <= n; i++) cin >> v[i];
    sort(v + 1, v + n + 1);//先将每一头牛的位置按顺序排列
    a = n - c;//满足当前分布状况的奶牛数量
    int L = 1, R = v[n] - v[1];//二分范围，左右端点，设置区间距离大小
    while (L + 1 < R) {
        int mid = L + R >> 1;
        if (check(mid)) L = mid;//找到合适的点就把左端点更新为当前点
        else R = mid;//否则右端点更新为当前点
    }
    if (check(R)) cout << R << '\n';//最后判断一下左右端点是否满足
    else cout << L << '\n';
    return 0;
}

P2249 【深基13.例1】查找

#include <bits/stdc++.h>  
using namespace std;
vector<int> vec;// 边长数组，这样我们就不用担心数据装不下了 
int main() {
	int n, m;
	int t;
	cin >> n >> m;
	int index;
    // 向数组尾部放入数据，因为这个特性，vector也可以当成stack用
	while(n--) cin >> t, vec.push_back(t);
	while(m--) {
		cin >> t;
        // 在序列里查找目标数据
		index = lower_bound(vec.begin(), vec.end(), t) - vec.begin();
        // 如果目标数据找到了，输出答案，注意我们的数组下标是从0开始的
		if (t == vec[index]) cout << index + 1 << ' ';
        // 没找到记得输出-1哦
		else cout << -1 << ' ';
	}
	return 0;
}

B3627 立方根

#include <bits/stdc++.h>
using namespace std;
//题目数据很大，超出int范围，需要用long long
typedef long long ll;  
int main()
{
	ll n;
	cin >> n;
	ll l = -100000, r = 100000;
	ll mid;
	while (l < r)
	{
		mid = (l + r) / 2;
		if (mid * mid * mid <= n) l = mid + 1;
		else r = mid;
	}
	if (r * r * r == n) cout << r;
	else cout << r-1;        //将r向下取整
	return 0;
}