二分查找

Question

问题背景：ljz在宿舍和舍友打保皇，在发牌阶段，ljz取牌插牌的速度很慢，而其他五个舍友取牌插牌手速很快，导致他的下家总是在等他取牌。

对此，lzj进行了反思：面对手中已然排好序的牌，ljz对于一张新来的牌x只会根据x的大小从最小的牌一直比较到最大的牌，直到找到第一个大于等于x的牌后，将牌插在这个地方。

他发现这样的O(n)的算法确实慢，但是他的猪脑都用来打牌了，已经过载了，希望你能帮他找到一种比较快速的查找方法，使得他的上家yzh不会对其进行宿舍暴力！

我们将问题抽象出来：

即给定一个有序的数组tr[i]，给你一个数字x，你需要输出数组中第一个大于等于x的下标

例如：

数组：1 2 2 2 3 3 4 5 6 10 10 12
下标：1 2 3 4 5 6 7 8 9 10 11 12

查询2 4 10

ljz作为万恶的甲方，突然想改需求，想换一种插入方式，因为他觉得同一种数值的牌在牌中的位置无所谓，所以对于一个新来的牌x，想插到同种数值的牌的最后的一个位置去，而不是第一个位置，你能帮他解决吗

例如：

数组：1 2 2 2 3 3 4 5 6 10 10 12
下标：1 2 3 4 5 6 7 8 9 10 11 12

查询2 4 10

Answer

显然，我们可以使用二分查找来满足他的需求

C++ STL的二分查找函数

如下函数，必须针对有序数组，有序不一定只是升序降序，也可以是按照某种cmp函数的排序方式

binary_search()返回bool值，判断是否存在
lower_bound()返回可插入的最小位置的迭代器

即返回第一个符号条件的元素的位置
upper_bound()返回可插入的最大位置的迭代器

即返回最后一个符合条件的元素的位置

例如：

数组：1 2 2 2 3 3 4 5 6 10 10 12
下标：1 2 3 4 5 6 7 8 9 10 11 12

	2	4	10	100
`binary_search()`	1	1	1	0
`lower_bound()`	2	7	10	13
`upper_bound()`	5	8	12	13

函数用法：

这三个函数的传参都是一样的，拿lower_bound()来举例子

lower_bound(itl, itr, x, cmp)，

itl和itr都是迭代器
x是待查询的数字
cmp是该数组的排序方式，不填的话，系统默认用的是从小到大的排序方式
函数返回的也是一个迭代器

数组名可以粗略地作为一个迭代器，指向的数组的第0号元素

所以如果想二分的范围是数组tr的1到n，则写成lower_bound(tr+1, tr+1+n, x)即可

正常的人的使用方法是：

从1开始存元素
对数组排序，从小到大排，sort(tr+1,tr+1+n);
再用lower_bound(tr+1,tr+1+n,x)-tr得到第一个大于等于x的下标

数组用法：

#include <bits/stdc++.h>
using namespace std;
#define MAX 300050
int n, x;
int tr[MAX];

int main(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    sort(tr + 1, tr + 1 + n);
    cin >> x;
    cout << lower_bound(tr + 1, tr + 1 + n, x) - tr << endl;
    return 0;
}

vector用法：

#include <bits/stdc++.h>
using namespace std;
#define MAX 300050
int n, x;

int main(){
    cin >> n;
    vector<int>v(n);
    for(int i = 0; i < n; ++i)cin >> v[i];
    cin >> x;
    cout << lower_bound(v.begin(), v.end(), x) - v.begin() << endl;
    return 0;
}

手撕lower_bound、upper_bound

手撕二分最需要注意的问题就是边界和判断函数的问题

我习惯于用左闭右开的区间，即[l, r],

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    cin >> x;
    int l = 1, r = n;
    while(l <= r){
        int mid = (l + r) / 2;
        if(tr[mid] >= x)r = mid - 1;
        else l = mid + 1;
    }
    cout << l << endl;
}

int main(){
    io;
    work();
    return 0;
}

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    cin >> x;
    int l = 1, r = n;
    while(l <= r){
        int mid = (l + r) / 2;
        if(tr[mid] > x)r = mid - 1;
        else l = mid + 1;
    }
    cout << l << endl;
}

int main(){
    io;
    work();
    return 0;
}

整数二分模版：

int l = 1, r = n;
while(l <= r){
  	int mid = (l + r) / 2;
  	if(judge(mid))l = mid + 1;
  	else r = mid - 1;
}

浮点数二分模版：

double l = 1, r = n;
while(r - l > 1e-6){
  	double mid = (l + r) / 2;
  	if(judge(mid))l = mid;
  	else r = mid;
}

二分答案

问题引入

Q:如何求单调连续函数 $y={(x+1)}^{\frac{1}{3}}-\frac{1}{2}$ 的零点?

A:利用零点存在性定理和二分答案

首先根据零点存在性定理，如果 $f=f(x)$ 在区间 $[l, r]$ 上的图像是连续的曲线，并且有 $f(l)*f(r)<0$ ，我们就说函数 $y=f(x)$ 在开区间 $(l,r)$ 内有零点，即存在 $x∈(l,r)$ 使得 $f(x)=0$
所以我们第一步要确定一个(l, r)，
然后我们需要确定mid = ( l + r ) / 2，计算f(mid)，根据与端点的正负性来判断零点的位置

什么时候该用二分答案

最最最典型的特征：求...最大值的最小 、 求...最小值的最大
答案在某个区间内，一般来说区间很大，暴力枚举会超时
容易判断某个答案是否符合条件
该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少…

经典的二分答案入门问题：木材加工

有n个长度为a[i]米的木头，你可以对木材进行切割，要保证切割得到的木材长度是整数且长度一样，都是x米，且数量是k个，对于长度不足x米的木头就直接扔掉，允许木头的剩余，问x最大是多少

n<=1e5 k<=1e8 a[i]<=1e8

我们分析一下题目

答案肯定是[1, 1e8]区间的一个数字，但暴力枚举肯定会T
很容易判断出某个答案是否合法，即如果指定x，很容易判断出n个木头能切出多少个长度为x的木头，如果大于等于k则说明x是符合答案的，否则是不符合答案的
具有单调性，目标小段越长，那能切出的段数越少，目标小段越短，能切出的段数越多。而最终需要K个，从而很容易判断一个答案行不行。

很符合要求，所以可以使用二分答案

二分答案的步骤：

确定l,r
写check函数，判断某个答案是否符合题目要求
根据check函数来进行区间的折半

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

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

bool judge(int mid){
    int sum = 0;
    for(int i = 1; i <= n; ++i){
        sum += tr[i] / mid;
    }
    if(sum >= k)return true;
    else return false;
}

int main(){
    cin >> n >> k;
    int maxn = 0;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
        maxn = max(maxn, tr[i]);
    }
    int l = 1, r = maxn;
    while(l <= r){
        int mid = (l + r) / 2;
        if(judge(mid))l = mid + 1;
        else r = mid - 1;
    }
    cout << l-1 << endl;
    return 0;
}

二分查找和二分答案的区别

二分查找：在一个已知的有序数据集上查找某些数
二分答案：答案存在于一个已知区间，满足区间的某个点之前的所有点是符合某种题目要求，而后面的点无法满足题目要求，即满足某种单调性，这个点即我们所求的答案，由于暴力枚举判断是会超时，所以需要利用折半的思想进行求解

洛谷题单

https://www.luogu.com.cn/training/111#problems