题目

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：每行的元素从左到右升序排列。 每列的元素从上到下升序排列

思路

从右上角开始搜索，如果当前值比目标值大，就向左走，如果当前值比目标值小，就向下走 注意这道题的边界

代码

public boolean searchMatrix(int[][] matrix, int target) { if(matrix==null || matrix.length==0|| matrix[0].length==0) { return false; } //从右上角开始找 int row = 0; int col = matrix[0].length-1; while(row<matrix.length&&col>=0){ if(matrix[row][col]>target){ col--; } else if(matrix[row][col]<target){ row++; } else{ return true; } } return false; }

思路

二分查找逐行查找

public boolean searchMatrix2(int[][] matrix, int target) { if (matrix.length == 0 || matrix[0].length == 0) { return false; } for (int i = 0; i < matrix.length; i++) { if (matrix[i][0] > target) { break; } if(matrix[i][matrix[i].length - 1] < target){ continue; } int col = binarySearch(matrix[i], target); if (col != -1) { return true; } } return false; } //二分查找 private int binarySearch(int[] nums, int target) { int start = 0; int end = nums.length - 1; while (start <= end) { int mid = (start + end) >>> 1; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { start = mid + 1; } else { end = mid - 1; } } return -1; }