这道题算是二分查找模板题，主要就是拿来练习二分查找，但同时也是可以用二叉查找树来写，时间复杂度和二分最优是一样的。
首先看看二分查找模板：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
int binarySearch(std::vector<int> &list, int target)
{
int len = list.size();
int l = -1, r = len, m;
while (l + 1 != r)
{
// m = (l + r) / 2; l + r 容易大数越界，所以改用下面的算法
m = l + (r - l) / 2;
if (list[m] < target)
l = m;
else if (list[m] > target)
r = m;
else
return m;
}
return -1;
}
|
题目
力扣：74. 搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
题解
两次二分查找
有题目可得矩阵是递增的，所以可以先通过二分查找到目标范围内的行然后再对这行二分查找判断是否存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// 二分查找定位目标行
int m = matrix.size(), n = matrix[0].size();
int top = -1, bottom = m, mid = 0, row;
int left = -1, right = n;
while (top + 1 != bottom)
{
mid = top + (bottom - top) / 2;
if (matrix[mid][0] <= target && target <= matrix[mid][n - 1])
break;
else if (matrix[mid][0] > target)
bottom = mid;
else
top = mid;
}
|
如果定位后出现 top > bottom 则没找到合适的行，目标不在矩阵内，直接返回 false 就好了。
1
2
3
|
// 没有找到合适的行
if (top > bottom)
return false;
|
接着就是对该行二分：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
row = mid;
left = -1, right = n;
// 在目标行内进行二分查找
while (left + 1 != right)
{
mid = left + (right - left) / 2;
if (matrix[row][mid] == target)
return true;
else if (matrix[row][mid] < target)
left = mid;
else
right = mid;
}
return false;
|
没有什么太大问题，整体代码：
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
|
bool searchMatrix_1(std::vector<std::vector<int>> &matrix, int target)
{
// 二分查找定位目标行
int m = matrix.size(), n = matrix[0].size();
int top = -1, bottom = m, mid = 0, row;
int left = -1, right = n;
while (top + 1 != bottom)
{
mid = top + (bottom - top) / 2;
if (matrix[mid][0] <= target && target <= matrix[mid][n - 1])
break;
else if (matrix[mid][0] > target)
bottom = mid;
else
top = mid;
}
// 没有找到合适的行
if (top > bottom)
return false;
row = mid;
left = -1, right = n;
// 在目标行内进行二分查找
while (left + 1 != right)
{
mid = left + (right - left) / 2;
if (matrix[row][mid] == target)
return true;
else if (matrix[row][mid] < target)
left = mid;
else
right = mid;
}
return false;
}
|
整体一次二分查找
由题可知，该矩阵是严格“从左到右递增，每列从上到下递增”的矩阵。
显然将每行首尾相连可以视为有序数组。
对于每一个元素的行列的计算如下：
1
2
3
|
int m = matrix.size(), n = matrix[0].size();
row = mid / n;
col = mid % n;
|
由此可以得出代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
bool searchMatrix_2(std::vector<std::vector<int>> &matrix, int target)
{
int m = matrix.size(), n = matrix[0].size();
int left = -1, right = m * n, mid;
int row, col;
while (left + 1 != right)
{
mid = left + (right - left) / 2;
row = mid / n;
col = mid % n;
if (matrix[row][col] < target)
left = mid;
else if (matrix[row][col] > target)
right = mid;
else
return true;
}
return false;
}
|
二叉搜索树
| 1 |
3 |
5 |
7 |
| 10 |
11 |
16 |
20 |
| 23 |
30 |
34 |
60 |
从右上角开始，向左在减小，向下在增大，又因为行列都递增。可以视从左上角开始为一个二叉搜索树：左支小于右支。
由此每次都可以淘汰掉一整行或一整列。
1
2
3
4
5
6
7
8
9
10
11
12
|
bool searchMatrix_3(std::vector<std::vector<int>> &matrix, int target)
{
int m = matrix.size(), n = matrix[0].size();
int i = 0, j = n - 1;
while (i < m && j >= 0)
{
if (matrix[i][j] == target)
return true;
matrix[i][j] > target ? j-- : i++;
}
return false;
}
|
用二叉搜索树算法的时间复杂度和空间复杂度都很优秀。
完整代码：c-cpp_studyProject/blob/main/learningCode/algorithm/search-a-2d-matrix.cpp
参考资料
- bilibili 搜索二维矩阵 | 编程面试必刷题