【二分查找的核心思想】● 二分查找的核心只围绕一个关键问题展开完成 mid 位置的条件判断之后目标答案究竟存在于左半区间还是右半区间。对该问题的不同判定结论直接决定了区间边界的修改逻辑从而衍生出各式各样的代码模板但万变不离其宗。● 不失一般性在二分查找中我们使用循环条件 while(leftright)并统一采用“左闭右开区间 [left, right)”的模型。在该模型下空区间对应 left rightleft 指向的元素在搜索范围内right 指向的元素不在搜索范围内这是后续所有逻辑推导的基础。● “左闭右开区间 [left, right)”二分模型的推荐代码1查找第一个 x 的数本代码为什么是找第一个 ≥x 的数而不是第一个 x 的数原因在于区间收缩的方向。/* The index starts from 0, with the range [0,n), call ffir(0,n,x) */ int ffir(int le,int ri,int x) { //find first x while(leri) { int midleri1; if(q[mid]x) lemid1; else rimid; } return le; }2查找最后一个 x 的数/* The index starts from 0, with the range [0,n), call ffir(0,n,x) */ int flas(int le,int ri,int x) { //find last x //Find the position of the first occurrence that x while(leri) { int midleri1; if(q[mid]x) rimid; else lemid1; } return le-1; //The position before the first occurrence of x is the last position of x }●“左闭右开区间 [left, right)” 的二分模型中right 永远指向第一个不在范围内的位置。所以基于此模型对于长度为 n 的数组对外调用形式为ffir(0, n, x)。即初始传入边界为 left0、rightn建立的初始搜索区间 [0,n)参数 x 是待查找的目标。​1当 q[mid] x 时mid 及其左边全部排除往右走 → le mid 1。2当 q[mid] ≥ x 时mid 可能是答案但左边可能还有更早的 ≥ x 的数往左收 → ri mid。最终 left 停在哪里​停在第一个使 q[mid] ≥ x 成立的位置。● 二分中的谓词函数就是用来判断 mid 位置对应的值是否满足某种条件的那个函数。在二分代码里谓词函数通常命名为 check(mid) 或直接写在 if 条件中其作用只有一个判断 mid 位置是否满足某一条件据此决定下一步向哪一侧收缩搜索范围。●谓词函数是二分的灵魂必须先定义再进行二分编码。不事先约定清楚你根本不知道二分返回的是什么。同样一个数组、同样一个目标值谓词函数从改成答案就可能截然不同。因此写二分的第一步永远是定义谓词函数。“左闭右开区间 [left, right)” 的二分模型中谓词约定如下1check(mid) true 代表下标为 mid 的元素满足目标性质答案下标一定不大于 mid即答案可以是 mid 本身也可以出现在 mid 左侧。2check(mid) false 代表下标为 mid 的元素不满足目标性质并且下标小于等于 mid 的所有元素也都不可能是答案答案只能出现在 mid 右侧。●谓词约定就是明确声明“二分中的 check(mid) 函数返回 true 或 false 分别代表什么含义以及这个返回值如何指导下一步的区间收缩”。谓词约定是二分的“设计文档”没有它代码就是一串没有意义的符号。【数组与调用方式】数据数组 q [1, 3, 5, 7, 9]长度 n 5有效下标 0, 1, 2, 3, 4。调用ffir(0, 5, 6)​ → 区间 [0, 5)包含下标 0,1,2,3,4正好是全部元素。目标找第一个 ≥ 6​ 的位置。1第一轮mid (05)/2 2整数除法下取整q[2] 5 6 → check 为假。5 6不可能是答案且它左边的所有数下标0,1也都小于6全部扔掉。更新left mid 1 3把 mid 踢出去right 不变还是5。此时区间 [3, 5) 包含下标 3, 4。2第二轮mid (35)/2 4q[4] 9 ≥ 6 → check 为真。9 ≥ 6可能是答案但左边可能还有更小的满足条件的数比如下标为 3 的数值 7。更新right mid 4把搜索上限拉到 mid 位置left 不变还是 3。此时区间 [3, 4) 只包含下标3。3第三轮mid (34)/2 3q[3] 7 ≥ 6 → check 为真。7 ≥ 6满足条件但左边已经没有元素了区间只剩这一个。更新right mid 3此时 left 3right 3left right循环结束。返回 left 3即第一个 ≥ 6 的数的下标是 3对应数值 7。【算法代码】→ https://www.luogu.com.cn/problem/U383691#include bits/stdc.h using namespace std; const int maxn1e55; int q[maxn]; int ffir(int le,int ri,int x) { //find first while(leri) { int midleri1; if(q[mid]x) rimid; else lemid1; } return le; } int flas(int le,int ri,int x) { //find last while(leri) { int midleri1; if(q[mid]x) rimid; else lemid1; } return le-1; } int main() { int n,m; scanf(%d%d,n,m); for(int i0; in; i) scanf(%d,q[i]); while(m--) { int x; scanf(%d,x); int leffir(0,n,x); if(q[le]!x) cout-1 -1endl; else { coutle ; coutflas(0,n,x)endl; } } return 0; } /* in: 6 3 1 2 2 3 3 4 3 4 5 out: 3 4 5 5 -1 -1 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/148748529