本文系统讲解二分查找的正确写法要点：边界条件、循环终止条件、中点更新逻辑，并以leetcode 74题为例，演示如何将二维矩阵线性化后进行o(log(mn))时间复杂度的精准二分搜索。
本文系统讲解二分查找的正确写法要点：边界条件、循环终止条件、中点更新逻辑，并以leetcode 74题为例，演示如何将二维矩阵线性化后进行o(log(mn))时间复杂度的精准二分搜索。
二分查找看似简单，却是算法实践中最容易出错的基础模板之一。常见错误包括：死循环（如 left = mid 未加 +1）、越界访问、漏判边界、条件分支遗漏 else 等。其核心难点不在于“找中间”，而在于精确控制搜索区间，确保每次迭代都严格收缩且不丢解。
✅ 正确二分查找的三大原则
-
统一使用闭区间
[left, right]或半开区间[left, right)，全程保持一致； -
循环条件与区间类型匹配：闭区间用
while left ，半开区间用 <code>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]
以下是精简、健壮、无分支遗漏的实现：
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1 # 闭区间 [0, m*n-1]
while left <= right:
mid = (left + right) // 2
val = matrix[mid // n][mid % n]
if val == target:
return True
elif val < target:
left = mid + 1 # ✅ 跳过 mid
else:
right = mid - 1 # ✅ 跳过 mid
return False? 为什么原代码失败？
- 第一次二分未处理
target == matrix[mid][0]后的break与后续逻辑衔接问题；- 第二次二分缺少
return True（仅写True无返回效果）；- 未校验空矩阵/空行等边界，导致运行时错误；
- 两次二分叠加虽理论可达 O(log m + log n)，但实际因两次独立循环、边界计算复杂，极易引入 off-by-one 错误。
? 关键注意事项
- 永远校验输入合法性：空矩阵、单行/单列场景需前置判断；
-
整数除法安全：Python 中
//向下取整，配合0起始下标天然适配；其他语言需注意负数取模行为； -
避免浮点运算：
mid = (left + right) // 2比(left + right) >> 1更清晰（现代编译器自动优化）； -
调试技巧：在循环内打印
(left, right, mid, val)，观察区间收缩是否单调、是否覆盖目标。
掌握这一模板后，无论是普通数组、旋转排序数组（LeetCode 33）、峰值查找（LeetCode 162），还是本题的二维映射，均可基于同一思维框架快速推导出正确解法——二分的本质，是利用有序性对解空间做对数级剪枝，而非机械套用公式。
