搜索二维矩阵Ⅰ

题意

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

这个矩阵具有以下特性:

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

样例

考虑下列矩阵:

[

    [1, 3, 5, 7],

    [10, 11, 16, 20],

    [23, 30, 34, 50]

]

给出 target = 3,返回 true

思路

可以先对每一行的第一列进行纵向二分查找,确定目标数大概在哪一行,然后再对那一行进行二分查找。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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 high = matrix.length - 1;
int low = 0;
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
if (matrix[mid][0] == target)
return true;
else if (matrix[mid][0] > target)
high = mid - 1;
else
low = mid + 1;
}
int row = mid;
if (matrix[mid][0] > target) {
if (mid > 0)
row = mid - 1;
else
return false;
}
low = 1;
high = matrix[0].length - 1;
while (low <= high) {
mid = (low + high) / 2;
if (matrix[row][mid] == target)
return true;
else if (matrix[row][mid] > target)
high = mid - 1;
else
low = mid + 1;
}
return false;
}
}

原题地址

LintCode:搜索二维矩阵Ⅰ

坚持原创技术分享,您的支持将鼓励我继续创作!