O(lgn) python solution


  • 0
    C
    class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        h_idx = self.binarySearch(nums, target, 1)
        l_idx = self.binarySearch(nums, target, 2)
        if h_idx == l_idx:
            return [-1, -1]
        else:
            return [l_idx, h_idx - 1]
    
    def binarySearch(self, nums, target, upper_or_lower):
        """
        :type upper_or_lower- 1: upper, 2: lower:
        :rtype: upper-index nums that is just larger than target, lower-first index of target
        """
        l = 0 
        h = len(nums) - 1
        while l <= h:
            m = (l + h) / 2
            if nums[m] > target:
                h = m - 1
            elif nums[m] < target:
                l = m + 1
            else:
                #same as target
                if upper_or_lower == 1:
                    #search for upper bound
                    l = m + 1
                elif upper_or_lower == 2:
                    #search for lower bound
                    h = m - 1
        return l

Log in to reply
 

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