74. Search a 2D Matrix

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, 50]
]
target = 3
Output: true

Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

---

给定一个矩阵，每行升序排列，并且下一行的最小值大于上一行的最大值，也就是说如果把矩阵按行展开，就是一个递增序列。问矩阵中是否存在一个数target。 很明显是二分搜索，先把每个行首元素看成一个新的有序数组，进行二分查找，确定所在行midr。然后在这一行进行二分搜索，查找target。 完整代码如下：

class Solution {
public:
    bool searchMatrix(vector<vector<int> >& matrix, int target)
    {
        if (matrix.size() == 0)
            return false;
        int m = matrix.size(), n = matrix[0].size();
        if (n == 0)
            return false;
        int l = 0, r = m – 1, midr = 0, midc = 0;
        while (l <= r) {
            midr = (l + r) / 2;
            if (target >= matrix[midr][0]) {
                if (target <= matrix[midr][n – 1])
                    break;
                l = midr + 1;
            }
            else
                r = midr – 1;
        }
        l = 0, r = n – 1;
        while (l <= r) {
            midc = (l + r) / 2;
            if (target == matrix[midr][midc])
                return true;
            if (target > matrix[midr][midc])
                l = midc + 1;
            else
                r = midc – 1;
        }
        return false;
    }
};

本代码提交AC，用时9MS。

二刷。更加规范的代码。首先找到目标数字所在的行，即找每一行开头数字中第一个大于目标数字的行，则前一行即为该数字所在的行，也就是l-1。为什么是l-1而不是r+1呢？这样想象：我们要找比target大的行首元素，如果mid一直小于target的话，则l会一直进行mid+1操作，直到l指向的元素大于target，此时前一行即为target所在行。不过要注意判断前一行是否存在的情况。

class Solution {
public:
	bool BinarySearch(vector<int>& vec, int target) {
		int l = 0, r = vec.size() - 1;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (vec[mid] == target)return true;
			if (vec[mid] < target)l = mid + 1; 
			else r = mid - 1;
		}
		return false;
	}
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
		int m = matrix.size();
		if (m == 0)return false;
		int n = matrix[0].size();
		if (n == 0)return false;

		int l = 0, r = m - 1;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (matrix[mid][0] == target)return true;
			if (matrix[mid][0] < target)l = mid + 1; 
			else r = mid - 1;
		}
		if (l < 1)return false;
		return BinarySearch(matrix[l - 1], target);
	}
};

本代码提交AC，用时16MS。