Python binary search O(logn)


  • 0
    D
    class Solution(object):
        def searchRange(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            left = self.bisect_left(nums, target)
            if left >= len(nums) or nums[left] != target:
                left = -1
            if left < 0:
                right = -1
            else:
                right = self.bisect_left(nums, target+1) - 1
            return [left, right]
    
        def bisect_left(self, nums, target):
            left, right = 0, len(nums)
            while left < right:
                mid = (left + right) / 2
                if nums[mid] >= target:
                    right = mid
                else:
                    left = mid + 1
            return left
    

Log in to reply
 

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