二分查找

问题

问题描述

有一个有序序列$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$不存在时)

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

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

        #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$

于是我们写出如下代码:

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

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

    

总结

定义1 二分性

在一个序列$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\}$,且序列$b$的相同值的位置都是连续的,如下所示:

$$\color{blue}{ \underbrace{b_1,b_2,b_3,\cdots,b_m}_{check = false}}, \color{red}{ \underbrace{b_{m+1},\cdots,b_n}_{check = true} }$$

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

如果序列b满足两个条件

• 只有两个值
• 相同值的位置都是连续

则说明序列$A$在函数$check$是具有二分性.其中$b_m,b_{m+1}$称为分界点

证明:

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

证明:

必要性显然. 充分性: 使用反证法: 假设序列$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.序列划分

二分的应用

二分查找应用分类详解

二分查找不仅仅是在有序数组中查找元素，它的本质是在具有单调性的空间中快速排除一半可能性来锁定目标。本文将二分查找的所有应用场景系统地分为五大类别。

一、基础定位：查位置与边界

核心操作： lower_bound、upper_bound
典型模式： 在有序序列中定位边界

1.1 基础查找与计数

在有序数组中进行各种查找操作：

• 查找一个特定的数字 - 判断元素是否存在
• 查找第一个大于或等于某个数的元素 - lower_bound 的经典应用
• 查找第一个大于某个数的元素 - upper_bound 的基础用法
• 查找最后一个小于或等于某个数的元素 - 前驱查找
• 统计某个数出现了多少次 - 利用上下界相减求频次

1.2 边界定位

经典实现：Vector + 二分的区间计数

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

        // 预处理：为每个值建立位置列表
map<int, vector<int>> pos;
void preprocess(const vector<int>& arr) {
    for (int i = 0; i < arr.size(); ++i) {
        pos[arr[i]].push_back(i);
    }
}

// 查询 x 在 [L,R] 中出现次数
int rangeCount(int L, int R, int x) {
    if (pos.find(x) == pos.end()) return 0;
    const vector<int>& idxs = pos[x];
    return upper_bound(idxs.begin(), idxs.end(), R) 
         - lower_bound(idxs.begin(), idxs.end(), L);
}

    

二、变体结构：特殊数组的特征查找

核心思路： 利用局部单调性，判断 mid 落在哪个单调段

2.1 旋转与断点

2.2 峰值与山脉

寻找"山峰"数组的顶点：对于一个数组先递增后递减的情况，虽然整个数组不是单调的，但我们可以利用山峰的性质来确定二分的搜索方向。

核心思想： 每次取中间位置 mid，通过比较 A[mid] 和它右边紧邻的元素 A[mid+1] 的关系，判断出 mid 正处于上坡还是下坡，从而确定真正的山峰在它的左边还是右边。

具体步骤：

1. 设置查找区间 [left, right] 为整个数组的下标范围
2. 取中间位置 mid
3. 比较 A[mid] 和 A[mid+1]：
   • 如果 A[mid] < A[mid+1]：说明 mid 正处在上坡阶段，山峰一定在 mid 的右边，更新 left = mid + 1
   • 如果 A[mid] > A[mid+1]：说明 mid 正处在下坡阶段，山峰就是 mid 本身或在 mid 的左边，更新 right = mid
4. 当 left 和 right 相遇时，那个位置就是山峰的顶点

示例代码：

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

        // 寻找山峰元素的下标
int findPeakElement(const std::vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[mid + 1]) {
            // mid 在上坡，山峰一定在右侧
            left = mid + 1;
        } else {
            // mid 在下坡或就是山峰，答案在左侧或就是 mid
            right = mid;
        }
    }
    // 循环结束时，left == right，指向山峰
    return left;
}

    

三、二分答案：解空间上的优化

核心思想： 答案具有单调性 —— 若答案 X 可行，则 X-1 也可行（或都不可行）
经典口诀： “最大化最小值”、“最小化最大值”

3.1 最值优化问题

猜答案（答案二分） 是处理优化问题的强大技巧：

• 解决"最大值最小化"问题

  • 例子：把一根很长的木头切成 k 段，怎么切才能让最长的那一段尽可能短？
  • 二分答案"最长段的长度"，检查能否在该限制下分成 k 段

• 解决"最小值最大化"问题

  • 例子：在一条路上装 k 个路灯，怎么装才能让两盏灯之间的最小距离尽可能远？
  • 二分答案"最小距离"，检查能否在该距离约束下放置 k 盏灯

3.2 第K值与统计

二分答案模板：

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14

        bool check(int mid) {
    // 检查 mid 是否可行
    // 根据具体问题实现
}

int binarySearchAnswer(int left, int right) {
    while (left < right) {
        int mid = (left + right + 1) >> 1;
        if (check(mid)) left = mid;
        else right = mid - 1;
    }
    return left;
}

    

四、数学与函数：数值解求解

核心思路： 在连续空间或数学规律中进行二分

4.1 方程求根

在小数（实数）上查找：

• 计算一个数的平方根，精确到指定的小数位
• 求解方程的近似解

4.2 复杂中位数

五、算法加速组件：复合应用

核心思路： 二分作为优化其他算法的子程序

5.1 动态规划优化

加速某些算法：二分查找可以将某些算法的时间复杂度显著降低，其中最经典的就是**最长上升子序列(LIS)**的优化。

最长上升子序列优化原理：

• 传统 DP 方法：O(N²) 时间复杂度
• 二分优化方法：O(N log N) 时间复杂度
• 核心思想：维护一个贪心数组，用二分查找替代线性扫描

5.2 高级技巧

LIS 二分优化实现：

        
1
2
3
4
5
6
7
8
9
10

        vector<int> lis_binary(vector<int>& nums) {
    vector<int> dp;  // 贪心维护的单调数组
    for (int x : nums) {
        auto it = lower_bound(dp.begin(), dp.end(), x);
        if (it == dp.end()) dp.push_back(x);
        else *it = x;
    }
    return dp;  // dp.size() 就是 LIS 长度
}

    

六、 高阶专题：二分与其他算法的深度结合

6.1 WQS 二分 (Alien’s Trick)

解决痛点： 求解"恰好选 K 个"的最值优化问题，通常配合 DP。 核心原理： 当答案关于 K 呈现凸性时，二分斜率(惩罚值)来切这个凸包。 经典题目： Luogu P2619

6.2 0/1 分数规划

核心模型： 最大化 $\frac{\sum a_i}{\sum b_i}$ 通用解法： 二分答案 $val$，检查 $\max(\sum (a_i - val \times b_i)) \ge 0$。

6.3 交互题中的二分

核心场景： Codeforces 交互题，通过 query 询问来缩小范围。

应用分类总览

练习建议

1. 入门练习： Luogu P2249 → AtCoder ABC248 D
2. 二分答案： Luogu P1824 → Luogu P1182
3. 算法优化： Luogu P1020

二分查找的威力在于将线性问题转化为对数复杂度。掌握这五大分类，你就掌握了二分查找在算法竞赛中的精髓。

练习题目

• luogu P1083
• luogu P2678
• luogu P1314
• luogu P1868
• luogu P1493
• luogu-P1419 寻找段落 tags: [二分,单调队列]
• hdu 6231
• poj 3273
• poj 3258
• poj 1905
• poj 3122
• luogu P1419 二分+单调队列