Python solution with two binary searches, finding the first and last occurrences respectively


  • 1
    N

    I found the video tutorial in the following link to be quite helpful:

    https://www.youtube.com/watch?v=OE7wUUpJw6I

    My solution is motivated also by this post:

    def searchRange(self, nums, target):
        def findFirstOccurence(A, x):
            left, right, result = 0, len(A) - 1, -1
            while left <= right:
                mid = (left + right) // 2
                if x == A[mid]:
                    result = mid
                    right = mid - 1
                elif x > A[mid]:    
                    left = mid + 1
                else: 
                    right = mid - 1         
            return result
    
        def findLastOccurence(A, x):
            left, right, result = 0, len(A) - 1, -1
            while left <= right:
                mid = (left + right) // 2
                if x == A[mid]:
                    result = mid
                    left = mid + 1
                elif x > A[mid]:    
                    left = mid + 1
                else: 
                    right = mid - 1             
            return result
    
        left, right = findFirstOccurence(nums, target), findLastOccurence(nums, target)
        
        return [left, right]
    

Log in to reply
 

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