二分法专题（普及组）

二分法是什么

数学定义：二分法（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]，

直到找到为止 。

案例大全

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;
}