16-line Python solution, symmetric and clean binary search, 52ms


  • 6
    K
    def searchRange(self, nums, target):
        def binarySearchLeft(A, x):
            left, right = 0, len(A) - 1
            while left <= right:
                mid = (left + right) / 2
                if x > A[mid]: left = mid + 1
                else: right = mid - 1
            return left
    
        def binarySearchRight(A, x):
            left, right = 0, len(A) - 1
            while left <= right:
                mid = (left + right) / 2
                if x >= A[mid]: left = mid + 1
                else: right = mid - 1
            return right
            
        left, right = binarySearchLeft(nums, target), binarySearchRight(nums, target)
        return (left, right) if left <= right else [-1, -1]

  • 0
    F

    @kitt
    maybe better

    def searchRange(self,nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            if target not in nums:
                return [-1,-1]
            l=0
            r=len(nums)-1
    
            while l<=r and l<len(nums)-1 and r>0:
                if nums[l]!=target:
                    l+=1
                if nums[r]!=target:
                    r-=1
                if nums[l]==target and nums[r]==target:
                    break
            if nums[l]==target:
                return [l,r]
            else:
                return [-1,-1]
    

  • 0
    R

    It is wrong. Solution is wrong. Test is wrong. Doesn't work for

    nums = [5,5,5,5,5,5,5,5,5,5,5]
    target = 25


  • 0
    L

    @fakenda the running time is not O(logn)


  • 0
    This post is deleted!

  • 0
    H

    @fakenda Time complexity is O(n)?


Log in to reply
 

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