One intuitive solution enclosed with an original but efficient one in C beating them all


  • 0
    bool search(int* a, int size, int target)
    {
        if(target<a[0] || target>a[size-1]) return false;
        int l=0, h=size-1;
        while(l < h)
        {
            int m = (l+h)/2;
            if(a[m] < target) l = m+1;
            else if(a[m] > target) h = m-1;
            else return true;
        }
        return a[l]==target;
    }
    
    //AC - 120ms - basic binary search;
    bool searchMatrix(int** matrix, int rSize, int cSize, int target)
    {
        for(int i = 0; i < rSize; i++)
        {
            if(search(matrix[i], cSize, target))
                return true;
        }
        return false;
    }
    

    //AC - 52ms - getting closer and closer to the target
    bool searchMatrix(int** matrix, int rSize, int cSize, int target)
    {
        int r=rSize-1, c=0;
        while(r>-1 && c < cSize)
        {
            if(matrix[r][c] < target) c++;
            else if(matrix[r][c] > target) r--;
            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.