LeetCode: 240. Search 2D matrix II

Write an efficient algorithm to search  m x n  matrix matrix One of the goals in target . The matrix has the following characteristics ：

The elements of each row are arranged in ascending order from left to right .
The elements of each column are arranged in ascending order 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

Tips ：

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matix[i][j] <= 109
All elements of each row are arranged in ascending order from left to right
All elements in each column are arranged in ascending order from top to bottom
-109 <= target <= 109

analysis ：

        Each row and column of the matrix are arranged in ascending order , The elements in the lower left and upper right corners of the matrix are very special , Take the upper right element as an example ： All numbers to the left of the element in this line are smaller than it , All the numbers below this element in this column are larger than it . We can use this property to reduce the search space . set up row = 0,column = matrix[0].size() - 1, take matrix[row][column] And target Contrast . If matrix[row][column] > target, Then we can exclude all the elements in this column , Because it is already the smallest element in the column , therefore column--; If matrix[row][column] < target, So we can exclude all the elements in this line , Because it is already the largest element in the row , therefore row++. By changing row and column, We can effectively reduce the search space , Increase of efficiency . Personally, I think there is a very good explanation , The essence of double pointer is to use the properties of the topic , Exclude some combinations that do not contain correct answers . Worthy of aftertaste .

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = 0, column = matrix[0].size() - 1;
        while(row < matrix.size() && column >= 0){
            if(matrix[row][column] < target)
                row++;
            else if(matrix[row][column] > target)
                column--;
            else
                return true;
        }
        return false;
    }
};