C++ Clean and Clear O(lgN + lgM) Solution.


  • 0
    F
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            if (matrix.empty() || matrix.front().empty())
                return false;
            int l = 0, h = matrix.size() - 1;
            while (l <= h)
            {
                int mid = l + (h - l)/2;
                if (matrix[mid][0] < target)
                    l = mid + 1;
                else if (matrix[mid][0] > target)
                    h = mid - 1;
                else
                    return true;
            }
            if (h == -1) 
                return false;
            int k = h;
            l = 0, h = matrix[k].size();
            while (l <= h)
            {
                int mid = l + (h - l)/2;
                if (matrix[k][mid] < target)
                    l = mid + 1;
                else if (matrix[k][mid] > target)
                    h = mid - 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.