题目
讲解
由于整个二维数组是有序的,根据题干可以得知,每一行是有序的,每一列是有序的,所以我们可以通过两次二分查找得到结果;
- 还是不变的y总二分模板
第一次二分用来查找是第几行,第二次用来查找是第几列;
题解
下边的题解展示了两种二分写法,注意第一次二分一定得是找小于等于target的值,不然会出现
[[1,2,3],[4,5,6],[7,8,9]]
如果target是3
这个二维数组第一次二分找的是大于等于3的行,会找到第二行
第二次二分就没什么需要判断的了,找小于等于或大于等于的都可以,
因为最后return时,还会进行一次判断
public boolean searchMatrix(int[][] matrix, int target) {
int temp_row = 0;
int temp_col = 0;
int row_l = 0;
int row_r = matrix.length-1;
while(row_l < row_r){
int row_mid = (row_l+row_r+1)/2;
//找到第一个小于或等于target的值
if(matrix[row_mid][0] <= target){
row_l = row_mid;
}else{
row_r = row_mid-1;
}
}
temp_row = row_l;
int col_l = 0;
int col_r = matrix[0].length-1;
while(col_l < col_r){
int clo_mid = (col_l+col_r)/2;
//找到第一个大于或等于target的值
if(matrix[temp_row][clo_mid] >= target){
col_r = clo_mid;
}else{
col_l = clo_mid + 1;
}
}
temp_col = col_l;
if(matrix[temp_row][temp_col] == target){
return true;
}else{
return false;
}
}