Python solution with 2 binary search


  • 0
    B

    taking this list for example [4 5 6 7 0 1 2]

    1: find the max index

    2: binary search in [left,max] or [max+1, len(nums)]

    def helper(self,nums,left,right):
    
        mid = (left+right)/2
        if left==mid:
            return left
    
        leftnum = nums[left]
        rightnum = nums[right]
    
        if  nums[mid]>leftnum:
            return self.helper(nums,mid,right)
        if nums[mid]<rightnum:
            return self.helper(nums,left,mid)
        #[4 5 6 7 0 1 2]
    
    def binary_search(self,nums,left,right,target):
    
        mid = (left+right)/2
        if nums[mid]==target:
            return mid
    
        if right -left==1:
            return -1
    
        if  nums[mid]>target:
            return self.binary_search(nums,left,mid,target)
    
        else :
            return self.binary_search(nums,mid,right,target)
    
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
    
        if nums[0]<nums[len(nums)-1]:
            return self.binary_search(nums,0,len(nums),target)
    
        maxIndex=self.helper(nums,0,len(nums)-1)
    
        print maxIndex
        if target>=nums[0]:
            return self.binary_search(nums,0,maxIndex+1,target)
    
        if target<=nums[-1]:
            return self.binary_search(nums,maxIndex,len(nums),target)
    
        return -1

  • 0
    A

    can we use code like bellow?

    if target in nums:
    return nums.index(target)
    else:
    return -1


Log in to reply
 

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