Python O(logn) binary search based solution. Easy to read


  • 0
    R
    class Solution:
        # @param A, a list of integers
        # @param target, an integer to be searched
        # @return a list of length 2, [index1, index2]
        def searchRange(self, A, target):
            if target is not None:
                ln = len(A)
                if target<A[0] or target>A[-1]:
                    return [-1, -1]
                else:
                    if target==A[ln/2]:
                        lower= ln/2
                        upper= ln/2
                        while lower>0:
                            lower-=1
                            if A[lower]!= target:
                                lower+=1
                                break
                        while upper< ln-1:
                            upper+=1
                            if A[upper]!= target:
                                upper-=1
                                break
                        return [lower,upper]
                    elif target<A[ln/2]:
                        return self.searchRange(A[:ln/2],target)
                    elif target>A[ln/2]:
                        temp = self.searchRange(A[ln/2 +1:],target)
                        if  temp == [-1,-1]:
                            return [-1,-1]
                        else:
                            return [ln/2+1 +temp[0] , ln/2 +1 + temp[1]]

  • 0
    J

    I think this is not O(logn), for example A = [1,1,1,1,1,1,1,1] target = 1, you have to check all values.


Log in to reply
 

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