28.Search a 2D Matrix-搜索二维矩阵（容易题）

搜索二维矩阵

题目

写出一个高效的算法来搜索 m × n矩阵中的值。

这个矩阵具有以下特性：

每行中的整数从左到右是排序的。 每行的第一个数大于上一行的最后一个整数。

样例

考虑下列矩阵：

[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] 给出 target = 3，返回 true

挑战

O(log(n) + log(m)) 时间复杂度

题解

和第14道题思路是一样的，先用二分法找到target所在行，再继续用二分法在行内查找O(log(n) + log(m))或遍历查找O(n + log(m))。

public class Solution { /** * @param 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) { if (matrix == null || matrix.length == 0) { return false; } int len = matrix[0].length; //target是否在该矩阵取值区间内 if (target < matrix[0][0] || target > matrix[matrix.length-1][len-1]) { return false; } int low = 0; int high = matrix.length-1; int mid = 0; while (low <= high) { mid = low + (high - low) / 2; if (matrix[mid][0] > target) { high = mid - 1; } else if (matrix[mid][len-1] < target) { low = mid + 1; } else { break; } } for (int i = 0; i < len; i++) { if (matrix[mid][i] == target) { return true; } } return false; } }

Last Update 2016.8.17