My 9ms C++ solution O(log(m)+lom(n)), without overflow


  • 1
    N

    The idea is sample, just use the binary search. First search which Row that the target might be, then search in that Row. Don't need to usem * n - 1, it may cause overflow.

        bool searchMatrix(vector<vector<int>>& matrix, int target) 
        {    
            int m = matrix.size(); // rows
            if (m == 0)
                return false;
            int n = matrix[0].size(); // columns 
            if (n == 0)
                return false;
            
            if (target > matrix[m-1][n-1] || target < matrix[0][0])
                return false;
            
            int first = 0, last = m - 1;
            while (first < last)
            {
                int mid = first + (last - first) / 2;
                if (target > matrix[mid][n - 1])
                    first = mid + 1;
                else 
                    last = mid;
            }
            // get the Row
            int r = last;
            
            first = 0;
            last = n - 1;
            // search the Row
            while (first <= last)
            {
                int mid = first + (last - first) / 2;
                if (target == matrix[r][mid])
                    return true;
                else if (target > matrix[r][mid])
                    first = mid + 1;
                else
                    last = mid - 1;
            }
            
            return false;
        }
    

    Thanks for reading.


Log in to reply
 

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