京公网安备11010502063487号给定一个 m × n 的矩阵，每一行从左到右升序，并且每一行的第一个数大于上一行的最后一个数。判断目标值是否在矩阵中。这个特殊的排列意味着：把所有行首尾相接，得到的是一个长度 m × n 的升序一维数组。所以可以直接对这个"虚拟"数组做二分查找，一维下标 k 对应第 k / n 行、第 k % n 列（n 是列数）。本文用真实数据展示把 n 写成 m 的后果，实测二分和逐行线性查找的耗时，给出五种语言的实现，并把二分做成分步演示。
完整题目见官方页面（链接在文末）。基准解是逐行用 in 线性查找，与二分是两种独立的写法。一共 15 组用例，覆盖：官方两个示例、单个元素、单行、单列、目标比所有数都小、比所有数都大、夹在两行之间的值、方阵与非方阵：
输入 [[[1,3,5,7],[10,11,16,20],[23,30,34,60]],3] 输出 true 输入 [[[1,3,5,7],[10,11,16,20],[23,30,34,60]],13] 输出 false 输入 [[[1]],1] 输出 true 输入 [[[1]],2] 输出 false 输入 [[[1,3]],3] 输出 true 输入 [[[1],[3]],3] 输出 true
一维下标换算成二维要除以列数 n：k / n 是行号，k % n 是列号。如果写成了行数 m，在方阵（m = n）上恰好正确，在非方阵上就错了：要么找错格子，要么下标越界。下面是真实结果：
# 换算下标时用行数 m 代替了列数 n 的写法（只有方阵才碰巧不出错） 3×4 矩阵 target=3: 该写法 -> True solve -> True 3×2 矩阵 target=7: 该写法 -> 下标越界 solve -> True 2×3 矩阵 target=5: 该写法 -> 下标越界 solve -> True 2×2 矩阵 target=5: 该写法 -> True solve -> True 随机 20000 个矩阵（其中方阵 3911 个）：该写法与正确答案不同（含越界）的有 12240 个（61.2%）
3×4 的官方示例，target = 3 碰巧对了（前几步命中的位置恰好没有错位），但 3×2 和 2×3 的矩阵上，该写法直接下标越界。方阵 2×2 上两种写法结果一致。在随机生成的 20000 个矩阵里（其中方阵只有 3911 个），该写法与正确答案不同（含越界）的有 12240 个，占 61.2%。所以只用方阵测试完全发现不了这个错误。
lo = 0，hi = m * n - 1。每一轮取中点 mid，换算出 mat[mid / n][mid % n]：等于目标就返回真；小于目标说明目标在后半，lo = mid + 1；否则在前半，hi = mid - 1。区间为空返回假。整个过程并不真的把矩阵拉平，只是用整除和取余做下标换算。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(mat, target): m, n = len(mat), len(mat[0]) lo, hi = 0, m * n - 1 # 把矩阵按行首尾相接，看成一个长度 m*n 的升序数组 while lo <= hi: mid = lo + (hi - lo) // 2 v = mat[mid // n][mid % n] # 一维下标 mid 对应第 mid // n 行、第 mid % n 列（n 是列数） if v == target: return True if v < target: lo = mid + 1 else: hi = mid - 1 return False
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[[1,3,5,7],[10,11,16,20],[23,30,34,60]],3] → true [[[1,3,5,7],[10,11,16,20],[23,30,34,60]],13] → false [[[1]],1] → true [[[1]],2] → false [[[1,3]],3] → true [[[1],[3]],3] → true
Java · 解法代码class Solution { public boolean searchMatrix(int[][] mat, int target) { int m = mat.length, n = mat[0].length; int lo = 0, hi = m * n - 1; // 把矩阵按行首尾相接，看成一个长度 m*n 的升序数组 while (lo <= hi) { int mid = lo + (hi - lo) / 2; int v = mat[mid / n][mid % n]; // 一维下标 mid 对应第 mid / n 行、第 mid % n 列（n 是列数） if (v == target) return true; if (v < target) lo = mid + 1; else hi = mid - 1; } return false; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[[1,3,5,7],[10,11,16,20],[23,30,34,60]],3] → true [[[1,3,5,7],[10,11,16,20],[23,30,34,60]],13] → false [[[1]],1] → true [[[1]],2] → false [[[1,3]],3] → true [[[1],[3]],3] → true
Go · 解法代码func searchMatrix(mat [][]int, target int) bool { m, n := len(mat), len(mat[0]) lo, hi := 0, m*n-1 // 把矩阵按行首尾相接，看成一个长度 m*n 的升序数组 for lo <= hi { mid := lo + (hi-lo)/2 v := mat[mid/n][mid%n] // 一维下标 mid 对应第 mid / n 行、第 mid % n 列（n 是列数） if v == target { return true } if v < target { lo = mid + 1 } else { hi = mid - 1 } } return false }
$ go build -o bin . && ./bin < cases.jsonl [[[1,3,5,7],[10,11,16,20],[23,30,34,60]],3] → true [[[1,3,5,7],[10,11,16,20],[23,30,34,60]],13] → false [[[1]],1] → true [[[1]],2] → false [[[1,3]],3] → true [[[1],[3]],3] → true
JavaScript · 解法代码function searchMatrix(mat, target) { const m = mat.length, n = mat[0].length; let lo = 0, hi = m * n - 1; // 把矩阵按行首尾相接，看成一个长度 m*n 的升序数组 while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); const v = mat[Math.floor(mid / n)][mid % n]; // 一维下标 mid 对应第 mid / n 行、第 mid % n 列（n 是列数） if (v === target) return true; if (v < target) lo = mid + 1; else hi = mid - 1; } return false; }
$ node run.js < cases.jsonl [[[1,3,5,7],[10,11,16,20],[23,30,34,60]],3] → true [[[1,3,5,7],[10,11,16,20],[23,30,34,60]],13] → false [[[1]],1] → true [[[1]],2] → false [[[1,3]],3] → true [[[1],[3]],3] → true
C++ · 解法代码#include <vector> using namespace std; class Solution { public: bool searchMatrix(vector<vector<int>>& mat, int target) { int m = mat.size(), n = mat[0].size(); int lo = 0, hi = m * n - 1; // 把矩阵按行首尾相接，看成一个长度 m*n 的升序数组 while (lo <= hi) { int mid = lo + (hi - lo) / 2; int v = mat[mid / n][mid % n]; // 一维下标 mid 对应第 mid / n 行、第 mid % n 列（n 是列数） if (v == target) return true; if (v < target) lo = mid + 1; else hi = mid - 1; } return false; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[[1,3,5,7],[10,11,16,20],[23,30,34,60]],3] → true [[[1,3,5,7],[10,11,16,20],[23,30,34,60]],13] → false [[[1]],1] → true [[[1]],2] → false [[[1,3]],3] → true [[[1],[3]],3] → true
共 15 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 15/15 Java 通过 15/15 Go 通过 15/15 JavaScript 通过 15/15 C++ 通过 15/15
矩阵每行 1000 个元素，元素总数分别为 1 万、10 万、100 万、400 万，找最后一个元素（逐行线性查找要看完几乎全部元素），每个规模取三次中最快的一次：
矩阵元素个数 m×n（找最后一个元素） | 暴力解 | 本文解法
10000 | 0.078 ms | 0.002 ms
100000 | 0.753 ms | 0.003 ms
1000000 | 7.855 ms | 0.012 ms
4000000 | 31.834 ms | 0.017 ms逐行查找（这里是 C 实现的 in）随元素个数线性增长，400 万时 35.0ms；二分只需要约 log₂(400万) ≈ 22 次比较，耗时是微秒量级，400 万时约 0.015ms，约 2300 倍。二分的耗时在这个范围内增长得很慢，小规模上的读数受计时精度影响，我没有细究。
Python 版本另外和逐行查找做了随机对拍：矩阵是随机的 1 到 5 行、1 到 5 列，按题目规则排好，target 60% 取自矩阵内，40% 随机取：
随机对拍 20000 组（1 到 5 行、1 到 5 列、按题目规则排好的矩阵（每行升序，且每行第一个数大于上一行最后一个数）；target 60% 取自矩阵内，40% 随机），solve 与 brute 的结果全部一致。
另外四种语言只在上面 15 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方的第二个示例，找 13（不在矩阵里）。矩阵按行连起来是 [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]，共 12 个数。mid = 5 对应第 1 行第 1 列，值 11，比 13 小，往后半找；mid = 8 对应第 2 行第 0 列，值 23，比 13 大，往前半；mid = 6 对应第 1 行第 2 列，值 16，比 13 大，hi 缩到 5，区间为空，没找到。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。