My O(logm+logn) solution in C++ (17ms)


  • 0
    Y
    class Solution {
    public:
        bool searchMatrix(vector<vector<int> > &matrix, int target) {
            if ( matrix.empty() || matrix[0].empty())
                return false;
            int l = 0;
            int r = matrix.size() - 1;
            int m = l + ((r - l) >> 1);
            while ( l <= r )
            {
                if ( matrix[m][0] == target )
                {
                    r = m;
                    break;
                }
                else if ( matrix[m][0] > target )
                    r = m - 1;
                else
                    l = m + 1;
                m = l + ((r - l) >> 1);
            }
            int k = r;
            if ( k < 0 )
                return false;
            if ( matrix[k][0] == target )
                return true;
    
            l = 0;
            r = matrix[k].size() - 1;
            m = l + ((r - l) >> 1);
            while ( l <= r )
            {
                if ( matrix[k][m] == target )
                {
                    r = m;
                    break;
                }
                else if ( matrix[k][m] > target )
                    r = m - 1;
                else
                    l = m + 1;
                m = l + ((r - l) >> 1);
            }
            return r >= 0 && matrix[k][r] == target;
        }
    };

Log in to reply
 

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