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.
这道题要求搜索一个二维矩阵，由于给的矩阵是有序的，所以很自然的想到要用二分查找法，我们可以在第一列上先用一次二分查找法找到目标值所在的行的位置，然后在该行上再用一次二分查找法来找是否存在目标值，代码如下：
// Two binary search class Solution { public: bool searchMatrix(vector<vector<int> > &matrix, int target) { if (matrix.empty() || matrix[0].empty()) return false; if (target < matrix[0][0] || target > matrix.back().back()) return false; int left = 0, right = matrix.size() - 1; while (left <= right) { int mid = (left + right) / 2; if (matrix[mid][0] == target) return true; else if (matrix[mid][0] < target) left = mid + 1; else right = mid - 1; } int tmp = right; left = 0; right = matrix[tmp].size() - 1; while (left <= right) { int mid = (left + right) / 2; if (matrix[tmp][mid] == target) return true; else if (matrix[tmp][mid] < target) left = mid + 1; else right = mid - 1; } return false; } };
当然这道题也可以使用一次二分查找法，如果我们按S型遍历该二维数组，可以得到一个有序的一维数组，那么我们只需要用一次二分查找法，而关键就在于坐标的转换，如何把二维坐标和一维坐标转换是关键点，把一个长度为n的一维数组转化为m*n的二维数组(m*n = n)后，那么原一维数组中下标为i的元素将出现在二维数组中的[i/n][i%n]的位置，有了这一点，代码很好写出来了：
// One binary search class Solution { public: bool searchMatrix(vector<vector<int> > &matrix, int target) { if (matrix.empty() || matrix[0].empty()) return false; if (target < matrix[0][0] || target > matrix.back().back()) return false; int m = matrix.size(), n = matrix[0].size(); int left = 0, right = m * n - 1; while (left <= right) { int mid = (left + right) / 2; if (matrix[mid / n][mid % n] == target) return true; else if (matrix[mid / n][mid % n] < target) left = mid + 1; else right = mid - 1; } return false; } };
本文转自博客园Grandyang的博客，原文链接：搜索一个二维矩阵[LeetCode] Search a 2D Matrix ，如需转载请自行联系原博主。
