二分查找

问题

问题描述

有一个有序序列$a_1,a_2,a_3,\cdots ,a_n$, 问第一个大于$k$的元素与位置是哪里.

样例输入

• 第一行两个整数$n(\leqslant 10^5),m(\leqslant 10^5)$,表示序列元素的数量,和有多少询问
• 第二行,$n$个数表示序列的元素,保证有序
• 接下来$m$行,询问的值

5 3
1 2 5 9 100
2
3
20

样例输出

• 每行两个数,表示每个询问的第一个$\geqslant$的值和对应的位置

2 2
5 3
100 5

解析1: 暴力

本问题是:在一个单调序列上查找$x$或$x$的后缀(当$x$不存在时)

显示对于每个询问,最简单的方法就是使用暴力查询,代码如下

#include <iostream>
using namespace std;
const int maxn=qe5+5;
int a[maxn];
int n,m;

int find(int val) {
    for (int i = 1; i <= n; i++)
    {
        if (a[i] >= val)
            return i;
    }
    return n+1;
}


int main() {
    cin >> n >> m;
    for(int i =1;i<=n;i++ )
        cin >> a[i];
    for(int i =1;i<=m;i++) {
        int num;
        cin >> num;
        int pos = find(num);
        if( pos == n+1)  //没有找到
            cout << "not found\n";
        else
            cout << a[pos] << " " << pos << "\n";
    }
    return 0;
}

上面的代码的时间复杂度为$O(n^2)$,显然会超时.

解析2: 二分法

面对样例$1,2,5,9,100$,这个序列是有序的

我们可以利用元素有序这条性质来加快我们的查询呢?

一个朴素的想法如下

面对样例,我们查询的位置的范围是$[1,6]$,为什么最后一个位置是$6$,不应该是$5$吗?因为我们有可能会查询到比最大值$100$还要大的元素,例如,$200$,那这个时候,我们应该返回的位置是$6$,$100$位置的后面一个位置.

同样,我们可以这样思考,我们把原序列末尾添加一个无穷大的值,改成

那么如果出现比最大的一个元素还大的查询,返回的位置就是$n+1$,同样如果得到返回值为$n+1$则知道,没有查询到需要的值,输出not found

如果需要查询的元素是$6$, 可以描述我们的问题为:$f(1,6,6)$,表示在区间$[1,6]$上找到第一个$\geqslant 6$位置,我们挑选到中间位置$(1+6) / 2 = 3$,值为$5$,又发则元素$5 \leqslant 6$,所以$5$和左边的元素都是比$6$小,所以范围$[1,3]$是对我们无用的范围,那么新的问就变成了:$f(4,6,6)$,在区间$[4,6]$上查询第一个$\geqslant 6$的位置

• 我们成功的将问题缩小了一半,将问题变得到更简单了
• 新的问题与原问题是相似的,这显然是递归
• 小朋友法:如果找到足够多的小朋友来帮我们解题,一定可以解出来.所以问题有解.

下面采用更抽象的方法,来思考问题,设问题为$f(l,r,val)$,表示在区间$[l,r]$上第一个$\geqslant val$的位置 .条件:保证区间$[l,r]$上必然存在一个值$\geqslant val$

则得到公式如下

其中$mid = \lfloor(l+r) \div 2\rfloor$,且显然$f(l,l,val) = l$

于是我们写出如下代码:

#include <iostream>
using namespace std;
const int maxn=1e5+5;
int a[maxn];
int n,m;

int mid(int l,int r) {
    return (l+r) >> 1; //这是最快的写法
}

//检查pos位置的值是否符合要求
bool check(int pos,int val){
    return a[pos] >= val;
}

//bs_find = binary search find
int bs_find(int l,int r,int val) {
    while( l < r) {
        int m = mid(l,r);
        if( check(m,val)) //成立
            r = m;
        else //不成立,抛弃左半边
            l = m+1;
    }
    return l ;
}


int main() {
    cin >> n >> m;
    for(int i =1;i<=n;i++ )
        cin >> a[i];
    for(int i =1;i<=m;i++) {
        int num;
        cin >> num;
        int pos = bs_find(1,n+1,num);
        if( pos == n+1)  //没有找到
            cout << "not found\n";
        else
            cout << a[pos] << " " << pos << "\n";
    }
    return 0;
}

总结

证明:

必要性显然.充分性: 根据描述,序列最多出现蓝红或红蓝,这种情况可以是边界,其它地方要么蓝,要么红,符合二分性的定义.

证明:

必要性显然. 充分性: 使用反证法: 假设序列$A$不符合引理$1$的描述,也就是会出现蓝红蓝的情况,但此时违反了引理$2$的描述,所以序列$A$符合引理$1$,引理$2$可以推出引理$1$.证毕.

推论2证明:

二分查找的正确性证明

开始证明:$\cal{Proof}.$

使用归纳法,证明bs_find(l,r,val)代码的正确性

只有1个元素的时候$a_1$,需要创建一个元素$a_2 = \infin$, 问题就变成求$f(1,2,val)$,取$m = (1+2) \gg 1 == 1$

分类讨论如下

1. 情况1: $check(1,val) = true \iff a_1 \geqslant val$,check函数成立,则问题变成$f(1,1,val) == 1$,得到正确答案
2. 情况2: $check(1,val) = false \iff a_1 \ngeqslant val$,check函数不成立,则问题变成$f(2,2,val) == 2$,得到正确答案

结论:当只有一个元素$a_1$时,函数bs_find可以得到正确答案

有两个元素$a_i,a_{i+1}$,且保证$check(i+1,val) = true$成立,取$m = (i+(i+1) / 2 = i$,说明当两个相当位置$i,i+1$,进行mid函数的运算后一定得到$i$,也就是较小的那个位置.

分类讨论如下

1. 情况1: $check(m=i,val) = true \iff a_i \geqslant val$,check函数成立,则问题变成$f(i,i,val) == i$,得到正确答案
2. 情况2: $check(m=i,val) = false \iff a_i \ngeqslant val$,check函数不成立,则问题变成$f(i+1,i+1,val) == i+1$,得到正确答案

结论:当只有两个元素$a_i,a_{i+1}$时,且$check(i+1,val)=true$成立时,函数bs_find可以得到正确答案

同理,有$3$个元素:$a_i,a_{i+1},a_{i+1}$,且保证$check(i+2,val)=true$成立时,函数bs_find(i,i+2,val)可以得到正确的答案

有$2k$(偶数)个元素的时候$a_1,a_2,\cdots,a_{2k}$, 且保证$check(2k,val)=true$成立时,取$m = (1+2k) \gg 1 = k$

分类讨论如下

1. 情况1: $check(m=k,val) = true \iff a_k \geqslant val$,check函数成立,则问题变成$f(1,k,val)$,
2. 情况2: $check(m=k,val) = false \iff a_k \ngeqslant val$,check函数不成立,则问题变成$f(k+1,2k,val)$

于是问题就变成是一个长度为$k$的子问题,问题正确性由子问题的正确性保证

同理,当有$2k+1$(奇数)个元素的时候$a_1,a_2,\cdots,a_{2k}$, 且保证$check(2k+1,val)=true$成立时,取$m = (1+2k+1) \gg 1 = k+1$,问题就变成是一个长度为$k+1$,或$k$的子问题,问题正确性由子问题的正确性保证

这样一直到分解,最后剩余的元素个数,一定会变成$2$或$3$,而这两个长度,已经验证成功.

证明完毕.$\cal{Q.E.D}$

一般化

TODO 没有解释清楚

具体什么样的情况下可以使用二分查询算法呢?

在一个序列$A = a_1,a_2,\cdots,a_n$上,有一个函数叫做$check(a_i)$,针对序列$A$形成的新的序列$B = b_1,b_2,\cdots,b_n$,其中$b_i = check(a_i) \in \{true,false\}$

序列

得到一个类似的如下的图:

若序列 存在某个位置

什么是单调性?

单调性的性质:

在一个单调性的序列上

1. 查询使函数$check(pos)$第一个成立的位置
2. 查询使函数$check(pos)$最后一个失败的后一个的位置

可以使用二分查询法

什么题目使用

1. 第一个$\geqslant x$元素的位置
2. 第一个$= x$元素的位置
3. 最后一个$\leqslant x$元素的位置
4. 求解数字$x$的数量
5. 求解满足数字$val \in [l,r]$的数量

经典模型

• 最小值最大,最大值最小问题
  • 1.序列划分

练习题目

• luogu P1083
• luogu P2678
• luogu P1314
• luogu P1868
• luogu P1493
• hdu 6231
• poj 3273
• poj 3258
• poj 1905
• poj 3122
• luogu P1419 二分+单调队列