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

搜索二维矩阵

1. 题目

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

   这个矩阵具有以下特性：

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

2. 样例

   考虑下列矩阵：

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

3. 挑战

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

4. 题解

   和第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

最后

以上就是等待小蘑菇为你收集整理的28.Search a 2D Matrix-搜索二维矩阵（容易题）的全部内容，希望文章能够帮你解决28.Search a 2D Matrix-搜索二维矩阵（容易题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。