Three python solutions with explanation


  • 0
    class Solution(object):
    def binarysearch(self,nums,left,right,target):
        while left<=right:
            mid=left+(right-left)/2
            if nums[mid]==target:
                return mid
            elif nums[mid]>target:
                right=mid-1
            else:
                left=mid+1
        return -1
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        #solution 1:using the attributes of List in python 
        '''if target not in nums:return [-1,-1]
        start=nums.index(target)
        ncount=nums.count(target)
        res=[start,start+ncount-1]
        return res'''
        #solution 2:binary search
        '''left,right=0,len(nums)-1
        res=[-1]*2
        while True:
            start=self.binarysearch(nums,left,right,target)
            if start!=-1:
                res[0]=start
                right=start-1
            else:
                break
        left,right=0,len(nums)-1
        while True:
            end=self.binarysearch(nums,left,right,target)
            if end!=-1:
                res[1]=end
                left=end+1
            else:
                break
        return res'''
        #solution 3
        left,right=0,len(nums)-1
        res=[-1]*2
        start=self.binarysearch(nums,left,right,target)  #firtly,binary search target, if find return index,else -1
        end=self.binarysearch(nums,left,right,target)
        while start!=-1: #then serach the left of target to find the smaller index
            res[0]=start
            right=start-1
            start=self.binarysearch(nums,left,right,target)
        left,right=0,len(nums)-1
        while end!=-1:#then serach the right of target to find the larger index
            res[1]=end #if exsit, assign to res[1]
            left=end+1
            end=self.binarysearch(nums,left,right,target)
        return res

Log in to reply
 

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