Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.
自己代码,自己想法,查看了别人的,被一顿教育,请看:
关于二分法的写法,被网上各帖子一顿教育,教育的 contents 在下面代码的注释中.
另一方面要注意的是:
- 用1次 BinarySearch,treat matrix as a Array
a[x] => matrix[x / 列][x % 列]
bool searchMatrix(vector<vector<int>>& A, int ta) {
// 用1次 BinarySearch,treat matrix as a Array
// n * m matrix convert to an array => matrix[x][y] => a[x * m + y]
// an array convert to n * m matrix => a[x] =>matrix[x / m][x % m];
if (A.empty() || A[0].empty())
return false;
int m = A.size(), n = A[0].size();
int lo = 0, hi = m * n - 1, mid, ro, co;
while (lo <= hi) { // 是<=
mid = lo + (hi - lo) / 2; //据说防溢出
ro = mid / n;
co = mid % n;
if (A[ro][co] == ta) return true; //紧凑的判断
else if (A[ro][co] > ta) hi = mid - 1;
else lo = mid + 1;
}
return false; // 退出循环就说明没找到!
}
最初自己想法,自己代码,超时,未通过(不仅是2次二分,更糟糕的是,我头脑中一直认为并使用的二分法写法,是错的,太可怕了)!
用两次二分.
(O(logn)) time, (O(1)) space.
bool searchMatrix(vector<vector<int>>& A, int ta) {
// 注意:我的这个代码是错的:二分写错,两次二分也不妥,但不错.
// 用两次 BinarySearch
// 第 1 次,应用于第 0 列,目的是找出元素在哪行,假如在 i 行
// 第 2 次,应用于第 i 行,目的是找出该行是否存在要找的元素 ta
int m = A.size(), n = A[0].size();
int lo = 0, hi = m - 1, loo = 0, hii = n - 1, mid;
// step1. 应用于第 0 列,目的是找出元素在哪行
while (lo < hi) {
mid = (lo + hi) / 2;
if (A[mid][0] < ta)
lo = mid + 1;
if (A[mid][0] > ta)
hi = mid - 1;
} // 若退出循环,lo==hi,认为元素在第 lo 行
if (A[lo][0] == ta)
return true;
// step2. 针对第 lo 行,用二分法,找出是否存在要找的元素 ta
while (loo < hii) {
mid = (loo + hii) / 2;
if (A[lo][mid] < ta)
loo = mid + 1;
if (A[lo][mid] > ta)
hii = mid - 1;
} // 若退出循环,loo==hii,查看 A[lo][loo] 是否为 target
if (A[lo][loo] == ta)
return true;
else
return false;
}