本文系统讲解二分查找的正确写法要点：边界条件、循环终止条件、中点更新逻辑，并以leetcode 74题为例，演示如何将二维矩阵线性化后进行o(log(mn))时间复杂度的精准二分搜索。
本文系统讲解二分查找的正确写法要点：边界条件、循环终止条件、中点更新逻辑，并以leetcode 74题为例，演示如何将二维矩阵线性化后进行o(log(mn))时间复杂度的精准二分搜索。
二分查找看似简单，却是算法实践中最容易出错的基础模板之一。常见错误包括：死循环（如 left = mid 未加 +1）、越界访问、漏判边界、条件分支遗漏 else 等。其核心难点不在于“找中间”，而在于精确控制搜索区间，确保每次迭代都严格收缩且不丢解。
✅ 正确二分查找的三大原则
-
统一使用闭区间
[left, right]或半开区间[left, right)，全程保持一致； -
循环条件与区间类型匹配：闭区间用
while left ，半开区间用while left ； -
更新边界时必须跳过已检查的
mid：若mid已被比较过，则left = mid + 1或right = mid - 1，避免死循环。
以 LeetCode 74 题为例——给定按行递增、行间严格递增的二维矩阵，要求 O(log(mn)) 搜索。关键洞察是：该矩阵本质上是一个长度为 m × n 的升序一维数组的“分页展示”。因此最优解是不单独定位行再搜列（易出边界/逻辑冗余），而是直接对虚拟一维下标 0 ~ m×n−1 做二分。
对应关系为：
- 一维下标
idx→ 行号idx // n，列号idx % n（n = len(matrix[0])） - 矩阵元素
matrix[idx // n][idx % n]
以下是精简、健壮、无分支遗漏的实现：
target == matrix[mid][0]
- 永远校验输入合法性：空矩阵、单行/单列场景需前置判断；
-
整数除法安全：Python 中
//向下取整，配合0起始下标天然适配；其他语言需注意负数取模行为； -
避免浮点运算：
mid = (left + right) // 2比(left + right) >> 1更清晰（现代编译器自动优化）； -
调试技巧：在循环内打印
(left, right, mid, val)，观察区间收缩是否单调、是否覆盖目标。
掌握这一模板后，无论是普通数组、旋转排序数组（LeetCode 33）、峰值查找（LeetCode 162），还是本题的二维映射，均可基于同一思维框架快速推导出正确解法——二分的本质，是利用有序性对解空间做对数级剪枝，而非机械套用公式。
