题目
编写一个高效的算法来搜索
m x n
矩阵matrix
中的一个目标值target
。该矩阵具有以下特性:
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
解题思路一
- 逐个遍历
代码展示
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; int n = matrix[0].length; for (int i = 0; i < m; i++){ for (int j = 0; j < n; j++){ if(matrix[i][j] == target){ return true; } } } return false; } }
解题思路
- 对每一行数据进行二分法查找
代码展示
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; int n = matrix[0].length; for (int i = 0; i < m; i++){ int left = 0, right = n - 1; while (left <= right){ int mid = (left + right) / 2; if(matrix[i][mid] == target){ return true; } if(matrix[i][mid] > target){ right = mid - 1; } else { left = mid + 1; } } } return false; } }