题目

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

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

示例:

现有矩阵 matrix 如下：

[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

题解

无官方题解

网友题解：

从最右上角的元素开始找，如果这个元素比target大，则说明找更小的，往左走；如果这个元素比target小，则说明应该找更大的，往下走。画个图看代码就很容易理解，总之就是从右上角开始找，如果矩阵的元素小了就往下走，如果矩阵元素大了就往左走。如果某个时刻相等了，就说明找到了，如果一直走出矩阵边界了还没找到，则说明不存在。 class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix == null || matrix.length < 1 || matrix[0].length < 1){ return false; } //起点为最左上角的元素 int row = 0, col = matrix[0].length - 1; //判断当前数组元素和target，如果当前大于target，往左走；小与target，往下走 while(row < matrix.length && col >= 0){ if(matrix[row][col] < target){ row++; }else if(matrix[row][col] > target){ col--; }else{ return true; } } //走出边界了还没找到，说明不存在，返回false return false; } }

执行用时 : 13 ms, 在Search a 2D Matrix II的Java提交中击败了86.52% 的用户

内存消耗 : 51.9 MB, 在Search a 2D Matrix II的Java提交中击败了34.62% 的用户

感想

写了个很慢的解答。。。思路就是很简单的分治，从左上角出发分为右侧、下侧、右下三部分去查找。

感觉看到别人从右上或者左下开始查找的思路，一下就发现自己的愚蠢了。。。右下和左下出发感觉就相当于二分法了，简单多了。

执行用时 : 66 ms, 在Search a 2D Matrix II的Java提交中击败了5.04% 的用户

内存消耗 : 51.9 MB, 在Search a 2D Matrix II的Java提交中击败了34.84% 的用户

class Solution { public boolean searchMatrix(int[][] matrix, int target) { return searchMatrixSub(matrix, target, 0, 0); } private boolean searchMatrixSub(int[][] matrix, int target, int row, int col){ if(matrix.length == 0) return false; else if(matrix[0].length == 0) return false; if(matrix[row][col] == target) return true; else if(matrix[row][col]>target) return false; else { boolean moreRow = (row<matrix.length-1); boolean moreCol = (col<matrix[0].length-1); if(moreRow&moreCol) return searchMatrixSub(matrix, target, row+1, col+1)||searchMatrixCol(matrix, target, row, col+1)||searchMatrixRow(matrix, target, row+1, col); else if(moreRow) return searchMatrixRow(matrix, target, row+1, col); else if(moreCol) return searchMatrixCol(matrix, target, row, col+1); else return false; } } private boolean searchMatrixRow(int [][]matrix, int target, int row, int col){ if(matrix[row][col] == target) return true; else if(matrix[row][col]>target) return false; else { if(row<matrix.length-1) return searchMatrixRow(matrix, target, row+1, col); else return false; } } private boolean searchMatrixCol(int [][]matrix, int target, int row, int col){ if(matrix[row][col] == target) return true; else if(matrix[row][col]>target) return false; else { if(col<matrix[0].length-1) return searchMatrixCol(matrix, target, row, col+1); else return false; } } }