Leetcode 74. Search two-dimensional matrix

74、 Search for a two-dimensional matrix

1） Title Description

Write an efficient algorithm to judge m x n Matrix , Is there a target value . The matrix has the following characteristics ：

• The integers in each row are arranged in ascending order from left to right .
• The first integer in each row is greater than the last integer in the previous row .

Example 1：

 Input ：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 Output ：true

Example 2：

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

Tips ：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4

2） analysis

Traveled through , Intra bank dichotomy .

• From the title, we can see , Traverse the matrix first by row , Matrix elements are non decreasing . Then, if the target value is less than the matrix row, traverse the first element first or greater than the last element , The target value must no longer be in the matrix ;
• If the target value may be in the matrix , Then traverse each row of the matrix , Compare the target value with the last element of the current row , Judge whether the target value may be in the current line ;
• If the target value is in the current line , Search the subscript of the corresponding element by dichotomy ;
• Judge whether the element corresponding to the searched subscript is equal to the target value .

3）C++ Code

class Solution {
    
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
    
        if(matrix[0][0]>target||matrix[matrix.size()-1][matrix[0].size()-1]<target)
            return false;
        int m=matrix.size();
        int n=matrix[0].size();
        for(int i=0;i<m;i++){
    
            if(matrix[i][n-1]<target)
                continue;
            else{
    
                int left=0;
                int right=n-1;
                while(left<=right){
    
                    int mid=(left+right)/2;
                    if(matrix[i][mid]<target)
                        left=mid+1;
                    else
                        right=mid-1;
                }
                return matrix[i][left]==target;
            }
        }
        return false;
    }
};