My solution, 16ms


  • 0
    J

    class Solution {
    public:

    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        
        if( matrix[0][0] > target || matrix.back().back() < target ) {
            return false;
        }
        int start = 0;
        int end = matrix.size() ;
        int middle = 0;
        
        while( end >= start) {
            middle = (start + end )/2;
            vector<int>& t = matrix[middle];
            
            if(t[0]>target && t.back()>target ) {
                end = middle -1;
            }else if( t[0] < target && t.back()< target) {
                start = middle + 1;
            }else {
                break;
            }
        }
        if( end < start ) {
            return false;
        }
        
        vector<int>& row = matrix[middle];
        end = row.size() ;
        start = 0;
        
        while( end >= start ) {
            middle = (start + end )/2;
            if( row[middle] > target) {
                end = middle -1;
            }else if( row[middle] < target ) {
                start = middle +1;
            }else {
                return true;
            }
        }
        return false;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.