Share straight-forward 53 ms python solution, binary search


  • 0
    R
    class Solution:
        # @param {integer[]} nums
        # @param {integer} target
        # @return {integer[]}
        def searchRange(self, nums, target):
            return [self.utilSearchLeft(0, len(nums)-1, nums, target), self.utilSearchRight(0, len(nums)-1, nums, target)]
    
        def utilSearchLeft(self, beg, end, arr, target):
    		# terminating condition, return index
            if (end - beg + 1) == 1:
                if arr[beg] == target:
                    return beg
                else:
                    return -1
    
    		# binary breakdown with computing median
            mid, med = self.utilGetMedian(beg, end, arr)
    
    		# odd number
            if len(mid) == 1:
                if med < target:
    				# search right half
                    if mid[0] < end:
                        return self.utilSearchLeft(mid[0]+1, end, arr, target)
                    else:
                        return -1
                elif med > target:
    				# search left half
                    if mid[0] > beg:
                        return self.utilSearchLeft(beg, mid[0]-1, arr, target)
                    else:
                        return -1
                else:
                    if mid[0] > beg:
    					# keep searching left excluding median
                        if self.utilSearchLeft(beg, mid[0]-1, arr, target) > -1:
                            return self.utilSearchLeft(beg, mid[0]-1, arr, target)
                        else:
                            return mid[0]
                    else:
                        return mid[0]
    
    		# even number
            else:
                if med < target:
    				# search right half
                    return self.utilSearchLeft(mid[1], end, arr, target)
                elif med > target:
    				# search left half
                    return self.utilSearchLeft(beg, mid[0], arr, target)
                else:
                    if (arr[mid[0]] != arr[mid[1]]):
    					# no such target exist
                        return -1
                    else:
                        if mid[0] > beg:
    						# keep search left excluding median
                            if self.utilSearchLeft(beg, mid[0]-1, arr, target) > -1:
                                return self.utilSearchLeft(beg, mid[0]-1, arr, target)
                            else:
                                return mid[0]
                        else:
                            return mid[0]
    
        def utilSearchRight(self, beg, end, arr, target):
    		
    		# terminating condition, return index
            if (end - beg + 1) == 1:
                if arr[beg] == target:
                    return beg
                else:
                    return -1
    
    		# binary breakdown with computing median
            mid, med = self.utilGetMedian(beg, end, arr)
    
    		# odd number
            if len(mid) == 1:
                if med < target:
    				# search right half
                    if mid[0] < end:
                        return self.utilSearchRight(mid[0]+1, end, arr, target)
                    else:
                        return -1
                elif med > target:
    				# search left half
                    if mid[0] > beg:
                        return self.utilSearchRight(beg, mid[0]-1, arr, target)
                    else:
                        return -1
                else:
                    if mid[0] < end:
    					# keep searching right excludind median
                        if self.utilSearchRight(mid[0]+1, end, arr, target) > -1:
                            return self.utilSearchRight(mid[0]+1, end, arr, target)
                        else:
                            return mid[0]
                    else:
                        return mid[0]
    
    		# even number
            else:
                if med < target:
    				# search right half
                    return self.utilSearchRight(mid[1], end, arr, target)
                elif med > target:
    				# search left half
                    return self.utilSearchRight(beg, mid[0], arr, target)
                else:
                    if (arr[mid[0]] != arr[mid[1]]):
                        return -1
                    else:
                        if mid[1] < end:
    						# keep search right excluding median
                            if self.utilSearchRight(mid[1]+1, end, arr, target) > -1:
                                return self.utilSearchRight(mid[1]+1, end, arr, target)
                            else:
                                return mid[1]
                        else:
                            return mid[1]
        
        def utilGetMedian(self, beg, end, arr):
            if (end-beg+1)%2 == 1:
                return [(beg+end)/2], arr[(beg+end)/2]
            else:
                return [(beg+end)/2, (beg+end)/2+1], (arr[(beg+end)/2] + arr[(beg+end)/2+1])/2.0

Log in to reply
 

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