题目概览编写一个高效的算法来搜索mxn矩阵matrix中的一个目标值target。该矩阵具有以下特性每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例 1输入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示例 2输入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 20输出false提示m matrix.lengthn matrix[i].length1 n, m 300-10^9 matrix[i][j] 10^9每行的所有元素从左到右升序排列每列的所有元素从上到下升序排列-10^9 target 10^9来源240. 搜索二维矩阵 II - 力扣LeetCode解题分析方法一二分法遍历每一行每一行用二分查找目标数。时间复杂度O(m*logn)空间复杂度O(1)class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m matrix.length, n matrix[0].length; for (int i 0; i m; i) { if (search(matrix, target, 0, n-1, i)) { return true; } } return false; } public boolean search(int[][] matrix, int target, int i, int j, int x) { if (j - i 1) { return matrix[x][i] target || matrix[x][j] target; } int mid (i j) / 2; if (matrix[x][mid] target) { return true; } if (matrix[x][mid] target) { return search(matrix, target, i, mid - 1, x); } return search(matrix, target, mid 1, j, x); } }方法二右顶点遍历我们可以从右上顶点开始遍历令该点为 ( i, j )则1. 当 matrix[ i ][ j ] target 时返回 true2. 当 matrix[ i ][ j ] target 时目标值一定不在当前行因此 i;3. 当 matrix[ i ][ j ] target 时目标值一定不在当前列因此 j--。时间复杂度O(mn)空间复杂度O(1)class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m matrix.length, n matrix[0].length; int i 0, j n - 1; while(i m j 0) { if (matrix[i][j] target) { return true; } if (matrix[i][j] target) { j--; } else { i; } } return false; } }