题目
搜索二维矩阵中是否包含特定元素,二维矩阵具有以下特性:
- 每行中的整数从左到右是排序的。
- 每行的第一个数大于上一行的最后一个整数
要求时间复杂度为O(log(n) + log(m)) ,原题链接:http://www.lintcode.com/zh-cn/problem/search-a-2d-matrix/
分析
既然二维矩阵是有序的,毫无疑问应当使用二分查找,先确定是否存在一行,能够满足line[0]>=target && line[line.length - 1] <= target,然后再在这一行中进行二分搜索。
代码
boolean findCol(int[] row, int target, int start, int end){
if(end == start+1){
if(row[start] == target) return true;
if(row[end] == target) return true;
return false;
}
int mid = (start+end)/2;
if(row[mid] == target) return true;
else if(row[mid] > target) return findCol(row, target, start, mid);
else return findCol(row, target, mid+1, end);
}
int findRow(int[][] matrix, int target, int start, int end){
if(start > end) return -1;
int mid = (start+end)/2;
int[] line = matrix[mid];
if(line[0]<=target && line[line.length-1] >=target){
return mid;
}
if(start == end){
return -1;
}
if(line[0]>target) return findRow(matrix, target, start, mid);
if(line[line.length-1]<target) return findRow(matrix, target, mid+1, end);
return -1;
}
/*
* @param matrix: matrix, a list of lists of integers
* @param target: An integer
* @return: a boolean, indicate whether matrix contains target
*/
public boolean searchMatrix(int[][] matrix, int target) {
// 有可能找不到包含target的行
int rowIndex = findRow(matrix, target, 0, matrix.length-1);
if(rowIndex<0) return false;
int[] line = matrix[rowIndex];
return findCol(line, target, 0, line.length-1);
}