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
.
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
if(m==0)
return false;
int n=matrix[0].length;
if(matrix[m-1][n-1]<target||matrix[0][0]>target)
return false; int first=0;
int last=m-1;
//二分法,判断target所在的行
//判断条件不能使<=,防止m==1时,while是死循环
while(first<last){
int center=(first+last)/2;
if(matrix[center][n-1]<target){
first=center+1;
}else if(matrix[center][n-1]==target){
return true;
}
else{
last=center;
}
} int left=0;
int right=n-1;
//二分法,判断target所属的列
while(left<=right){
int center=(left+right)/2;
if(matrix[first][center]==target)
return true;
else if(matrix[first][center]<target){
left=center+1; }else{
right=center-1;
}
}
return false;
}
}