【原题】
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
Given target = 3, return true. 【解释】 给定一个二维数组每一行有序,行与行之间有序,给定一个target,要求返回该元素是否在二维数组中。 【思路】 有序自然想到二分查找。但这题需要使用两次二分查找,首先二分查找到行,然后在该行中再使用二分(刚开始,使用顺序查找得到行号也可以过)。假设二维矩阵为mxn,则算法的复杂度为O(logm+logn)O(logm+logn).
public class Solution {
//查找列
public boolean binarySearchCol(int[][] matrix, int row, int target){
int left=0,right=matrix[row].length-1;
while(left<right){
int mid=(left+right)/2;
if(matrix[row][mid]==target)
return true;
if(matrix[row][mid]>target)
right=mid-1;
else
left=mid+1;
}
return matrix[row][left]==target;
}
public boolean searchMatrix(int[][] matrix, int target) {
int m=matrix.length;
if(m==0) return false;
int n=matrix[0].length;
if(n==0) return false;
int left=0,right=m-1;
/*注意这个二分查找要找到可能在的行,所以没有找到对应的target不能直接返回false,
而要在最可能的一行单重继续查找*/
while(left<right){
int mid=(left+right+1)/2;
if(matrix[mid][0]>target)
right=mid-1;
else if(matrix[mid][0]<target)
left=mid;
else return true;
}
return binarySearchCol(matrix, left,target);
}
}