二分查找

发表于2026-01-26|更新于2026-02-12

|浏览量:

二分查找是常见的算法,但是我发现我经常无法区分应当使用哪种变形来计算答案,因此这里做一下讲解.

标准写法

ll l=___,r=___;
while(l<=r){
	ll mid=l+(r-l)>>1;
	if(____) l=mid+1;
	else r=mid-1;
}

判断条件的选择

判断条件可以理解为,每次要淘汰哪一部分,并通过l,r指针的移动来确定的

前提条件:假设现在我们有一个升序的数组

比如:我现在要查找第一个大于等于key的值
那么我们的条件就应该是每次循环都删去小于key的值,不能删去大于的,因为答案可能在这里面

于是我们的条件就写成:if(a[mid]<key) l=mid+1;
为什么是mid+1?因为l表示的是左边界,左边界移动了,就相当于淘汰了左边的小于key的值

同理,我们在写找第一个大于当前值时,只要改成<=即可

那么反过来呢?

没错,把条件和操作全反过来即可.现在我们要找第一个小于等于key的值
所以我们每次淘汰的是大于key的值

条件变为:if(a[mid]>key) r=mid-1;

答案的取值

弄清楚了怎么写条件,我们还需要弄清楚最后l还是r指向的才是答案.

我的方法是,假设第一次指向的就是正确答案,那么哪个指针指向就是正确答案.
所以也是就if对应的变化的指针,就是答案.

比如查找大于等于key时,if条件后面变化的是l,所以答案就是l所对应的值.

其他技巧

学习二分主要的目的不是为了二分查找,而是为了二分答案.判断条件有可能会更复杂.但是核心还是上面哪两点,首先知道我要删的是什么,其次答案会等于什么位置

最后,使用二分时不要忘记检查数据是否以及排序,答案是否一定满足升序关系,再加上适量的边界检查,二分就能拿下啦!

C++自带的二分

C++中,能使用lower_bound和upper_bound的有set,multi_set(多重集合),数组,vector

前者查找第一个大于等于key的值,后者找第一个大于key的值(先保证数组有序才行)

那么小于或小于等于呢?

小于可以先查大于等于的,再向前一步
小于等于可以先查大于的,再向前一步

文章作者: ZestfulYK

文章链接: https://zestfulyk.github.io/ZestfulYK-blog/2026/01/26/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 ZestfulYK的Blog！

相关推荐

格雷码及其应用

题目输入n,构造长度为$2^n-1$的序列,使得下面在这个式子的值最小 \sum_{i=1}^{2^n-1}a_{i-1} \oplus a_i方法:每组相邻元素最好二进制中只有一位不一样打表结果: 1234n=1 0 1n=2 0 1 3 2n=3 0 1 3 2 6 7 5 4 1 0 2 3 7 6 4 5 所以暴力或者按结论使用格雷码 12345678910111213#include <iostream>using namespace std;int main() { int n; cin >> n; int m = 1 << n; for (int i = 0; i < m; ++i) { cout << (i ^ (i >> 1)); if (i < m - 1) cout << ' '; } cout << endl; return 0...

简单题对于简单题目，最好还是仔细一点，或者使用最暴力的解法，而不是投机取巧，或者构造高级方法，通常样例数据都是片面的，常常会有坑。 sleeping through classes 比如这一题，数据没有包含i+k中间有1的情况，直接i+=k导致错误。中等题目中等题目就需要强观察力和trick技巧了 Niko’s Tactical Cards 这一道题目是动态规划的变种，虽然要求每一步最优，但是可能发生最小值突然转变成最大值的情况，因此，计算最小值也是必要的。只要计算这两个值就行了。 Kanade’s Perfect Multiples 这题希望我们构造一个满足要求的B，这个就有点类似于筛法求素数了，实际上两者的代码几乎是一样的，但是在做的时候要注意区分原始数据和v数组，一个一个遍历就行了，找不到就可以直接退出，因为不然当前确定的最小值就无法被覆盖了。 Merging the Sets 你想选择其中的一些集合（可能一个都不选，也可能全部都选），使得 1 和 m 之间的每个整数都包含在个所选集合中的至少一个中。思维误区，不用一边读入一边判断，因为数据保证$l\leq 2*1...

公式S=\sum_{i=1}^{m}a_ib_i=a_mB_m-\sum_{i-1}^{m-1}(a_{i+1}-a_i)B_i

C++几何计算(保姆级教程)

版权说明此文章的所有代码均由qinye_leaf 勤叶大佬收集整理，感谢喵Orz Orz Orz 初始化由于双精度和单精度存在精度问题，所以补能直接判断是否为0或者相等，那么怎么办呢？我们可以取绝对值，然后和一个非常小的数字比较代码示例：12// 浮点数精度阈值(根据题目要求调整，通常1e-8)const double EPS = 1e-8; 符号函数判断正负号的函数，但是是浮点数数版本的 12345// 符号函数：判断浮点数正负int sgn(double x) { if (fabs(x) < EPS) return 0; return x > 0 ? 1 : -1;} 构造函数介绍解释一下构造函数的用法，这里可以直接赋初始值，方便初始化 1234Point(double x_ = 0, double y_ = 0) : x(x_), y(y_) {}//那么我们可以这么来定义一个变量Point p1(2.0,3.0);Point p2; 如果不传参数，那么就是直接得到初始值0,0,要是有值的化就是直接赋值，这样...

DP(01)最长不下降子序列及其变种

变种一就是01串,方法在下面,懒得解释了,自己看注释吧题目:问最少能把01串划成几个0101…类型的字符串12345678910111213//关键点,类似最长不下降子序列的题目,但是由于是01串,只要管有几个0结尾和1结尾的串就好了ll c0=0,c1=0;for(int i=0;i<t.length();i++){ if(t[i]=='1'){ if(c0) c0--;//接到0结尾的后面 c1++;//多了一个以1结尾的串 } else{ if(c1) c1--;//接到1结尾的后面 c0++;//多了一个以0结尾的串 } } return c0+c1; 变种二是有有限个结尾的dp 例如牛客周赛题目:把字符串变成相邻字母的ASCALL码之差都一样,求最小操作次数因为只有26个字母,所以可以直接滚动数组+dp,然后设dp[i][j]表示以第i位结尾改成char('a'+j)的最少修改次数,或者也可以设成改为char('...

DP习题笔记-二进制拆分

题目描述给定一个非负整数 $n(0\leq n \leq 10^7)$，求有多少个长为 30 的非负整数序列 a ,满足 $\sum_{i=0}^{29}2^i*a_i=n$由于答案可能很大，请将结果对 998244353 取模后再输出。解法看到题目，第一反应就是一个完全背包的动态规划题目，所以直接打表解决，不过发现超时了，那么怎么办呢？输出前30个数得到如下结果：1231 2 2 4 4 6 6 10 10 14 14 20 20 26 26 36 36 46 46 60 60 74 74 94 94 114 114 140 140 166观察得到，每两个数是一样的，如果去重的话得到： 11 2 4 6 10 14 20 26 36 46 60 每一次的差正好都在前面出现过且这个差的位置刚好是n/2，那么可以得到递推式子：$$\begin{cases}dp[i]=dp[i-1]\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{i为奇数}\dp[i]=dp[i-1]+dp[i/2]\ \ \ \ \ \ \text{i为偶...