240. Search a 2D Matrix II

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The 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.
 

Example 1:


Input: 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]], target = 5
Output: true
Example 2:


Input: 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]], target = 20
Output: false
 

Constraints:

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matix[i][j] <= 109
All the integers in each row are sorted in ascending order.
All the integers in each column are sorted in ascending order.
-109 <= target <= 109

这题解法很多，像遍历所有肯定可以求出来，只是时间复杂度比较高O(m*n),而且没有利用到纵横有序的性质。

我一开始利用了水平排序的性质，在符合条件的每一行进行二分搜索，可以通过，但是耗时比较高。

后来经过了解，能够使用排除法来减少搜索的区域。假设我们选取左下角，则和它一行的所有的数字，都比它大，而和它一列的数字，都比它小。我们可以利用这个特性，每次来排除一行或者一列，让搜索的矩形区域不断变小直到找到符合条件的值。

当target比左下角值大的时候，说明它一列的值肯定不符合条件，我们不用去搜索该区域，所以可以去除掉这列，把左下角向右移动。 当target比左下角值小的时候，说明它一行的值肯定不符合条件，我们不用去搜索该区域，所以可以去除掉这行，把左下角向上移动。

如此往复，直到左下角等于taget或者行列的索引超出范围。

class SearchA2DMatrixII : public Solution {
public:
    void Exec() {
        
    }
    bool searchMatrix(vector<vector<int>>& matrix, int target){
        int row = matrix.size() - 1;
        int col = 0;
        while (col <= matrix[0].size() - 1 && row >= 0) {
            if (matrix[row][col] == target) return true;
            if (target > matrix[row][col]) {
                col++;
            } else {
                row--;
            }
        }
        return false;
    }
    bool searchMatrixBinarySearch(vector<vector<int>>& matrix, int target) {
        if (target < matrix[0][0] ||
            target > matrix[matrix.size() - 1][matrix[0].size() - 1])
            return false;
        for (auto &row : matrix) {
            if (row[0] > target || row[row.size() - 1] < target)
                continue;
            int left = 0, right = row.size() - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (row[mid] == target)
                    return true;
                if (target > row[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return false;
    }
};