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.
解法1：据题意，矩阵以行主序展开到一维后就是一个排序数组，因此可以用二分查找，将当前查找index转换为二维坐标即可。
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty() || matrix[0].empty()) return false; int m = matrix.size(); int n = matrix[0].size(); int left = 0, right = m * n - 1; while (left <= right) { int mid = (left + right) >> 1; int i = mid / n, j = mid % n; if (target == matrix[i][j]) return true; else if (target < matrix[i][j]) right = mid - 1; else left = mid + 1; } return false; } };
解法2：可以根据target和每一行第一个数的比较进行二分查找，先确定target所在目标行：若target==nums[i][0]，直接返回true；若target>nums[i][0]，则target必在[i,m)的那几行；否则target在[0,i)的那几行。最后可以确定target具体在哪一行；在确定了具体的行后，再对该行进行二分查找，确定target具体位置。
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty() || matrix[0].empty()) return false; if(target < matrix.front().front() || target > matrix.back().back()) return false; int m = matrix.size(); int n = matrix[0].size(); int above = 0, below = m - 1; while(above <= below) { int mid = (above + below) >> 1; if(target == matrix[mid][0]) return true; else if(target < matrix[mid][0]) below = mid - 1; else above = mid + 1; //虽然实际上此时target可能恰好mid这行，但是above还是必须设置为mid+1，否则形成死循环 } //注意不能使用matrix[above]，因为target>matrix[mid][0]时target有可能恰好在matrix[mid]中，此时above=mid+1是不行的 return binarySearch(matrix[below], target); } private: bool binarySearch(const vector<int>& nums, int key) { int n = nums.size(); int left = 0, right = n - 1; while (left <= right) { int mid = (left + right) >> 1; if (key == nums[mid]) return true; else if (key < nums[mid]) right = mid - 1; else left = mid + 1; } return false; } };
如果target是和matrix[i][n-1]比较来确定target所在行的话，则上面代码注释地方恰好要使用matrix[above]了：
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty() || matrix[0].empty()) return false; if(target < matrix.front().front() || target > matrix.back().back()) //处理矩阵只有一个元素的情况 return false; int m = matrix.size(); int n = matrix[0].size(); int above = 0, below = m - 1; while(above <= below) { int mid = (above + below) >> 1; if(target == matrix[mid][n - 1]) return true; else if(target < matrix[mid][n - 1]) below = mid - 1; //虽然实际上此时target可能恰好mid这行，但是below还是必须设置为mid-1，否则形成死循环 else above = mid + 1; } //注意不能使用matrix[below]，因为target>matrix[mid][0]时target有可能恰好在matrix[mid]中，此时below=mid-1是不行的 return binarySearch(matrix[above], target); } private: bool binarySearch(const vector<int>& nums, int key) { int n = nums.size(); int left = 0, right = n - 1; while (left <= right) { int mid = (left + right) >> 1; if (key == nums[mid]) return true; else if (key < nums[mid]) right = mid - 1; else left = mid + 1; } return false; } };