【二分查找的核心思想】
● 二分查找的核心只围绕一个关键问题展开：完成 mid 位置的条件判断之后，目标答案究竟存在于左半区间，还是右半区间。对该问题的不同判定结论，直接决定了区间边界的修改逻辑，从而衍生出各式各样的代码模板，但万变不离其宗。
● 不失一般性，在二分查找中，我们使用循环条件 while(left<right)，并统一采用“左闭右开区间 [left, right)”的模型。在该模型下，空区间对应 left == right，left 指向的元素在搜索范围内，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(le<ri) { int mid=le+ri>>1; if(q[mid]<x) le=mid+1; else ri=mid; } 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(le<ri) { int mid=le+ri>>1; if(q[mid]>x) ri=mid; else le=mid+1; } 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)。即初始传入边界为 left=0、right=n，建立的初始搜索区间 [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)” 的二分模型中，谓词约定如下：
（1）check(mid) = true 代表下标为 mid 的元素满足目标性质，答案下标一定不大于 mid，即答案可以是 mid 本身，也可以出现在 mid 左侧。
（2）check(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 = (0+5)/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 = (3+5)/2 = 4，q[4] = 9 ≥ 6 → check 为真。
9 ≥ 6，可能是答案，但左边可能还有更小的满足条件的数（比如下标为 3 的数值 7）。
更新：right = mid = 4（把搜索上限拉到 mid 位置），left 不变，还是 3。
此时区间 [3, 4) 只包含下标3。
（3）第三轮
mid = (3+4)/2 = 3，q[3] = 7 ≥ 6 → check 为真。
7 ≥ 6，满足条件，但左边已经没有元素了（区间只剩这一个）。
更新：right = mid = 3，此时 left = 3，right = 3，left == right，循环结束。
返回 left = 3，即第一个 ≥ 6 的数的下标是 3，对应数值 7。
【算法代码】→ https://www.luogu.com.cn/problem/U383691
#include <bits/stdc++.h> using namespace std; const int maxn=1e5+5; int q[maxn]; int ffir(int le,int ri,int x) { //find first while(le<ri) { int mid=le+ri>>1; if(q[mid]>=x) ri=mid; else le=mid+1; } return le; } int flas(int le,int ri,int x) { //find last while(le<ri) { int mid=le+ri>>1; if(q[mid]>x) ri=mid; else le=mid+1; } return le-1; } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=0; i<n; i++) scanf("%d",&q[i]); while(m--) { int x; scanf("%d",&x); int le=ffir(0,n,x); if(q[le]!=x) cout<<"-1 -1"<<endl; else { cout<<le<<" "; cout<<flas(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
