189 8069 5689
这篇文章主要介绍“C++怎么实现搜索一个二维矩阵”，在日常操作中，相信很多人在C++怎么实现搜索一个二维矩阵问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++怎么实现搜索一个二维矩阵”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
为万柏林等地区用户提供了全套网页设计制作服务，及万柏林网站建设行业解决方案。主营业务为网站建设、网站制作、万柏林网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！
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.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
这道题要求搜索一个二维矩阵，由于给的矩阵是有序的，所以很自然的想到要用二分查找法，可以在第一列上先用一次二分查找法找到目标值所在的行的位置，然后在该行上再用一次二分查找法来找是否存在目标值。对于第一个二分查找，由于第一列的数中可能没有 target 值，该如何查找呢，如果是查找第一个不小于目标值的数，当 target 在第一列时，会返回 target 所在的行，但若 target 不在的话，有可能会返回下一行，不好统一。所以可以查找第一个大于目标值的数，也就是总结帖中的第三类，这样只要回退一个，就一定是 target 所在的行。但需要注意的一点是，如果返回的是0，就不能回退了，以免越界，记得要判断一下。找到了 target 所在的行数，就可以再次使用二分搜索，此时就是总结帖中的第一类了，查找和 target 值相同的数，也是最简单的一类，分分钟搞定即可，参见代码如下：
解法一：
class Solution {
public:
bool searchMatrix(vector>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int left = 0, right = matrix.size();
while (left < right) {
int mid = (left + right) / 2;
if (matrix[mid][0] == target) return true;
if (matrix[mid][0] < target) left = mid + 1;
else right = mid;
}
int tmp = (right > 0) ? (right - 1) : right;
left = 0;
right = matrix[tmp].size();
while (left < right) {
int mid = (left + right) / 2;
if (matrix[tmp][mid] == target) return true;
if (matrix[tmp][mid] < target) left = mid + 1;
else right = mid;
}
return false;
}
}; 当然这道题也可以使用一次二分查找法，如果我们按S型遍历该二维数组，可以得到一个有序的一维数组，只需要用一次二分查找法，而关键就在于坐标的转换，如何把二维坐标和一维坐标转换是关键点，把一个长度为n的一维数组转化为 m*n 的二维数组 (m*n = n)后，那么原一维数组中下标为i的元素将出现在二维数组中的 [i/n][i%n] 的位置，有了这一点，代码很好写出来了：
解法二：
class Solution {
public:
bool searchMatrix(vector>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int m = matrix.size(), n = matrix[0].size();
int left = 0, right = m * n;
while (left < right) {
int mid = (left + right) / 2;
if (matrix[mid / n][mid % n] == target) return true;
if (matrix[mid / n][mid % n] < target) left = mid + 1;
else right = mid;
}
return false;
}
}; 这道题其实也可以不用二分搜索法，直接使用双指针也是可以的，i指向0，j指向列数，这样第一个被验证的数就是二维数组右上角的数字，假如这个数字等于 target，直接返回 true；若大于 target，说明要减小数字，则列数j自减1；若小于 target，说明要增加数字，行数i自增1。若 while 循环退出了还是没找到 target，直接返回 false 即可，参见代码如下：
解法三：
class Solution {
public:
bool searchMatrix(vector>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int i = 0, j = (int)matrix[0].size() - 1;
while (i < matrix.size() && j >= 0) {
if (matrix[i][j] == target) return true;
else if (matrix[i][j] > target) --j;
else ++i;
}
return false;
}
}; 到此，关于“C++怎么实现搜索一个二维矩阵”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注创新互联网站，小编会继续努力为大家带来更多实用的文章！