二分查找算法如何应用于搜索？

3.二分算法 核心本质：找 “边界”，而非 “单调性” 误区：认为 “只有有序数组才能二分”，实际只要区间能划分为 “满足性质” 和 “不满足性质” 两部分，即可二分； 核心：每次缩小一半区间，且保证 “答案始终在区间内”，直到区间长度为 1（整数）或足够小（浮点数）。 3.1 整数二分：边界处理是难点 \[\begin{aligned} & \text{mid} = \frac{l+r+1}{2} \\ & if(check(mid)) = \begin{cases}true; & [mid,r],l=mid \\false; & [l,mid-1],r=mid-1\end{cases} \end{aligned} \] \[\begin{aligned} & \text{mid} = \frac{l+r}{2} \\ & if(check(mid)) = \begin{cases}true; & [l,mid],r=mid \\false; & [mid+1,r],r=mid+1\end{cases} \end{aligned} \] 1.两种模板：对应两种边界场景​ 场景 1：找 “满足性质的左边界”（如 “第一个≥x 的数”）； 场景 2：找 “满足性质的右边界”（如 “最后一个≤x 的数”）； 关键区别：计算mid时是否加 1（避免死循环）。 2.模板 1：找左边界（第一个满足 “q [mid] ≥ x” 的数）​ 适用场景：求 “起始位置”（如数组[1,2,2,3,3,4]中，3 的起始下标 3）。 代码模板（C++）： bool check(int x) {/* ... */ } // 检查x是否满足某种性质 // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用： int bsearch(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1;//如果下方else后面是l则这里加1 if (check(mid)) l = mid; else r = mid - 1;//左加右减 } return l; } 解释：如果mid在红色区域，那么应该满足X≥mid（抽象简化），X应该在mid和r之间取值。否则X < mid，那么X应该在l和mid-1之间取值 计算中间索引mid：int mid = l + r + 1 >> 1;，这里l + r + 1 >> 1是将l + r + 1的结果右移一位，相当于除以 2 并向下取整。当check(mid)为true时，说明满足条件的值在mid及其右边的区间，所以更新l = mid；当check(mid)为false时，说明满足条件的值在mid左边的区间，所以更新r = mid - 1。这部分逻辑在二分查找中对于将区间划分为[l, mid - 1]和[mid, r]这种划分方式是合理的。然而，函数最后return 1;是有问题的，正常二分查找应该返回找到的满足条件的索引值或者在未找到时返回特定标识（如 -1 等），直接返回 1 不能正确表示查找结果。 3.模板 2：找右边界（最后一个满足 “q [mid] ≤ X” 的数）​ 适用场景：求 “终止位置”（如数组[1,2,2,3,3,4]中，3 的终止下标 4）。 代码模板（C++）： // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用： int bsearch(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1;//左加右减 } return l; } 解释：如果mid在绿色区域，那么应该满足X ≤ mid，X应该在l和mid之间取值。否则X > mid，那么X应该在mid+1和r之间取值。 计算中间索引mid：int mid = l + r >> 1;，同样是计算中间索引，将l + r右移一位得到中间值。