问题背景

编写一个高效的算法来搜索$m\times n$矩阵$matrix$中的一个目标值$target$。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

数据约束

• $m==matrix.length$
• $n==matrix[i].length$
• $1\le n,m\le 300$
• $-10^9<=matrix[i][j]<=10^9$
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• $-10^9\le target\le 10^9$

解题过程

元素有序，首先想到二分法。然而本题中没有办法利用二分先确定待查找元素所在行或所在列，所以只能退而求其次遍历行或者列，再对另一个方向上用二分查找，这样做时间复杂度是 $O(mlogn)$ 或 $O(nlogm)$。

如果从矩阵右上角出发，每次判断当前元素与目标值的大小关系，那么在没找到的情况下，每次都能排除掉一行或一列。事实上因为每次查找失败时，都能明确往哪个方向进行下一步搜索，所以这个做法相当于查找抽象的二叉搜索树，时间复杂度是 $O(m+n)$。理论上这样做在数据规模特别大的情况下会优于上一种思路，但是本题中数据量不是很大，两者区别不明显。

具体实现

按行或列二分查找

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;for(int i = 0; i < m; i++) {int left = 0, right = n - 1;while(left < right) {int mid = left + ((right - left) >>> 1);if(matrix[i][mid] < target) {left = mid + 1;} else {right = mid;}}if(matrix[i][left] == target) {return true;}}return false;}
}

抽象二叉搜索树

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int i = 0, j = matrix[0].length - 1;while(i < matrix.length && 0 <= j) {if(matrix[i][j] == target) {return true;}if(matrix[i][j] < target) {i++;} else {j--;}}return false;}
}