Description

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 in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
Given target = 5, return true.

Given target = 20, return false.

Explain

这道题题意就是给一个每行都是从左到右排好序的，每列也是从上到下排好序的矩阵。然后给一个值，询问这个值是否在矩阵里面。唯一有效信息就是从左到右和从上到下是排好序的。说明每行的第一个值只要比目标值大，那么这一行就可以忽略不计了。它后面的行也是。那么我们可以先确定一个行的范围。确定行的范围后，由于这个值有可能出现在任一行。我们可以枚举每一可行行，然后二分查找。

Code

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty()) return false;
        if (matrix[0].empty()) return false;
        int start = 0;
        for (start = 0; start < matrix.size(); start++) {
            if (matrix[start][0] > target) break;
        }
        
        bool res = false;
        helper(matrix, 0, start == matrix.size() ? start - 1 : start, res, target);
        return res;
        
    }
    
    void helper(vector<vector<int>>& matrix, int left, int right, bool& res, int target) {
        if (res) return;
        if (left > right) return;
        int mid = (right - left) / 2 + left;
        int _left = 0, _right = matrix[mid].size() - 1;
        while(_left <= _right) {
            int _mid = (_right - _left) / 2 + _left;
            if (matrix[mid][_mid] > target) _right = _mid - 1;
            else if (matrix[mid][_mid] < target) _left = _mid + 1;
            else {
                res = true;
                return;
            }
        }
        
        helper(matrix, left, mid - 1, res, target);
        helper(matrix, mid + 1, right, res, target);
    }
};