Sharing my 12ms C++ solution


  • 0
    T
    class Solution {
    private:
        int searchMatrix1(vector<vector<int>>& matrix, int target, int up, int down)
        {
            if(up>down)
                return -1;
            else
            {
                int pivot = up + (down-up)/2;
                if(target>=matrix[pivot][0] && target<=matrix[pivot].back())
                    return pivot;
                else if(target < matrix[pivot][0])
                    return searchMatrix1(matrix, target, up, pivot-1);
                else
                    return searchMatrix1(matrix, target, pivot+1, down);
            }
        }
        
        bool searchMatrix2(vector<vector<int>>& matrix, int row, int target, int left, int right)
        {
            if(left>right)
                return false;
            else
            {
                int pivot = left + (right-left)/2;
                if(target==matrix[row][pivot])
                    return true;
                else if(target<matrix[row][pivot])
                    return searchMatrix2(matrix, row, target, left, pivot-1);
                else
                    return searchMatrix2(matrix, row, target, pivot+1, right);
            }
        }
        
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int m = matrix.size();
            if(m==0)
                return false;
            int n = matrix[0].size();
            if(n==0)
                return false;
            int row = searchMatrix1(matrix, target, 0, m-1);
            if(row==-1)
                return false;
            return searchMatrix2(matrix, row, target, 0, n-1);
        }
    };

Log in to reply
 

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