二分查找-搜索二维矩阵

矩阵的两个性质保证了将矩阵按行展开成一维数组后数组是严格递增的。因此我们可以直接用二分查找将二维坐标映射为一维索引时间复杂度为O(log(mn))空间复杂度为O(1)。坐标映射公式一维索引idx对应二维坐标行号row idx / nn为矩阵列数列号col idx % n二分查找边界left 0right m * n - 1为什么要用(left right) 1很多新手在写二分查找时会用最直观的写法int mid (left right) / 2;但在工业级代码如 JDK 源码中几乎看不到这种写法取而代之的是int mid (left right) 1; // 或 int mid left (right - left) / 2;1. 整数溢出Java 中int类型是 32 位有符号整数取值范围为[-2^31, 2^31 - 1]即[-2147483648, 2147483647]。当left和right都接近int最大值时int left 2147483647; int right 2147483647; // left right 4294967294超出 int 范围溢出为负数 int sum left right; // sum -2 int mid sum / 2; // mid -1完全错误在二分查找中错误的负数索引会直接导致数组越界异常ArrayIndexOutOfBoundsException程序崩溃。2.无符号右移从根源解决溢出Java 提供了两种右移运算符有符号右移高位补符号位正数补 0负数补 1等价于除以 2向下取整无符号右移无论正负高位统一补 0将数值视为 32 位无符号整数处理原理验证对于溢出后的负数sum -2二进制补码为11111111 11111111 11111111 11111110sum 1高位补 1结果为-1错误sum 1高位补 0结果为2147483647正确即(2147483647 2147483647) / 2 2147483647对于非负整数(left right) 1完全等价于(left right) / 2但永远不会出现溢出问题完美解决了二分查找的索引计算风险。3. 三种写法的全面对比写法优点缺点适用场景(left right) / 2可读性高存在整数溢出风险不安全仅适用于left right不超过int最大值的场景left (right - left) / 2无溢出可读性较好运算步骤多性能略差所有场景新手友好(left right) 1无溢出、代码简洁、性能最优新手可读性差工业级代码、JDK 源码、高性能场景延伸二分查找的其他安全写法除了无符号右移还有一种经典的安全写法int mid left (right - left) / 2;原理通过变形避免直接相加left (right - left) / 2 (2left right - left) / 2 (left right) / 2这种写法从根源上避免了left right的溢出可读性比更高适合新手理解也是面试中的标准写法。性能对比(left right) 1仅需一次加法 一次位运算JVM 可直接优化为机器指令性能最优left (right - left) / 2需要一次减法 一次除法 一次加法性能略差但现代 JVM 优化后差异极小实战搜索二维矩阵的完整优化1. 边界处理代码中必须处理矩阵为空、单行、单列等极端情况避免空指针异常if (matrix null || matrix.length 0 || matrix[0].length 0) { return false; }2. 二分查找的循环条件while (left right)适用于闭区间[left, right]每次循环都会检查mid最终left right时退出代表未找到while (left right)适用于开区间[left, right)需要额外处理最后一个元素容易出错不推荐新手使用3. 示例验证以题目示例矩阵为例[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60] ]展开为一维数组[1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]查找target 3mid最终命中索引1对应row0, col1返回true查找target 13遍历完所有区间未命中返回false总结核心结论int mid (left right) 1是二分查找中安全、高效、无溢出的中间索引计算方法是 JDK 源码的标准写法。原理本质利用无符号右移将溢出的负数视为无符号整数保证计算结果正确同时保持最优性能。替代方案left (right - left) / 2是新手友好的安全写法可读性更高适合面试场景。应用场景所有二分查找算法如搜索二维矩阵、有序数组查找、旋转数组查找等都应使用安全写法避免整数溢出。拓展思考1. 为什么题目中的「非严格递增」不影响二分虽然每行是「非严格递增」但「每行第一个元素大于前一行最后一个元素」的性质保证了整个矩阵展开后是严格递增的因此二分查找的逻辑完全成立。2. 其他语言的对应写法PythonPython 整数无溢出直接用mid (left right) // 2即可C用mid left (right - left) / 2避免溢出无运算符JavaScript用mid Math.floor((left right) / 2)注意位运算会截断为 32 位整数3. 二分查找的常见坑整数溢出必须使用安全写法计算mid循环条件错误left right与left right的区别边界更新错误left mid 1/right mid - 1与left mid/right mid的选择坐标映射错误行号 / 列号的计算逻辑mid / n与mid % n完整代码/** * 搜索二维矩阵 * param matrix 满足行内非严格递增、行首严格大于前行尾的矩阵 * param target 目标值 * return target 是否在矩阵中 */ public boolean searchMatrix(int[][] matrix, int target) { // 边界处理矩阵为空、行空、列空直接返回false if (matrix null || matrix.length 0 || matrix[0].length 0) { return false; } int m matrix.length; // 矩阵行数 int n matrix[0].length; // 矩阵列数 int left 0; // 二分左边界一维索引 int right m * n - 1; // 二分右边界一维索引 // 闭区间二分查找[left, right] while (left right) { // 安全计算中间索引无符号右移避免int溢出 int mid (left right) 1; // 一维索引转二维坐标 int row mid / n; int col mid % n; int current matrix[row][col]; if (current target) { // 找到目标值返回true return true; } else if (current target) { // 目标值在右半区间更新左边界 left mid 1; } else { // 目标值在左半区间更新右边界 right mid - 1; } } // 遍历完所有区间未找到返回false return false; }