easy to understand binary search solution O(logN).


  • 0
    D
    def searchRange(self, A, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            l, r, m = 0, len(A), 0
            s, e = 0, 0
            while l < r:
                m = l + (r - l) // 2
                if A[m] == target:
                    s, e = m, m
                    while e < r-1 and A[e] == A[e + 1]:  # right limit
                        e += 1
                    while s > l and A[s] == A[s - 1]:   # left limit
                        s -= 1
                    return [s,e]
        
                if A[m] > target:
                    r = m
                else:
                    l = m + 1
            return [-1, -1]

Log in to reply
 

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