This is O(log n ) right? divide and conquer for a range


  • 0
    B
    def findRangeRecursive(li,start,end):
            mid=(start+end)//2
            if start==end:
                if li[start]==target:
                    return [start,end]
                else:
                    return [-1,-1]
    
            rangeL=findRangeRecursive(li,start,mid)
            rangeR=findRangeRecursive(li,mid+1,end)
    
            if rangeL[0]==-1 and rangeR[0]==-1:
                return rangeL
            elif rangeL[1]==-1:
                return rangeR
            elif rangeR[0]==-1:
                return rangeL
            else:
                return [rangeL[0],rangeR[1]]
    

    it will return the proper range if called with findRangeRecursive(A,0,len(A)-1)

    i guess it is O (log n) by the master equation


  • 1
    S

    Sorry I don't think this is an O(logN) solution. In each function call, it calls itself twice, each with half the original input. So the running time of this functions call is:

    T(n) = 2T(n/2) + constant
    

    This is essentially O(N) according to Case 1 in Master's theorem.


Log in to reply
 

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