Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example, Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3
, return true
.
解题思路
二分搜索。把矩阵看成是一维数组,建立一维数组序号与二维数组坐标之间的对应关系:
m=(pos−1)/col;
n=(pos−1)%col;
然后进行普通的二分搜索。
实现代码
// Runtime: 1 ms
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0) {
return false;
}
int row = matrix.length;
int col = matrix[0].length;
int left = 1;
int right = row * col;
while (left <= right) {
int mid = left + (right - left) / 2;
int m = (mid - 1) / col;
int n = (mid - 1) % col;
if (matrix[m][n] > target) {
right = mid - 1;
} else if (matrix[m][n] < target) {
left = mid + 1;
} else {
return true;
}
}
return false;
}
}