Python 40ms solution with brief comments; 97.54%


  • 0
    Z
    class Solution(object):
        def searchRange(self, nums, target):
            """
            :type nums: List[int]; target: int; rtype: List[int]
            """
            if not nums: return [-1, -1]
    
            lenN = len(nums)
            #step 1 find the init pivot
            pivot = self.bSearch(nums, 0, lenN-1, target)
    
            if pivot == -1: return [-1, -1]
    
            ret = [pivot, pivot]
    
            #step 2 push toward left
            lastFound = pivot
            while lastFound != -1:
                ret[0] = lastFound
                lastFound = self.bSearch(nums, 0, lastFound-1, target)
    
            #step 3 push toward right
            lastFound = pivot
            while lastFound != -1:
                ret[1] = lastFound
                lastFound = self.bSearch(nums, lastFound+1, lenN-1, target)
    
            return ret
    
        def bSearch(self, n, l, r, t):
            """
            : @n: nums list; @l,r: left and right index; @t: target
            : @@return: index or -1 if not found
            """
            while l<=r:
                mid = l + (r-l)//2
                if   n[mid] > t: r = mid-1
                elif n[mid] < t: l = mid+1
                else: return mid
            return -1

Log in to reply
 

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