Python solution with 2 binary search

  • 0

    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)
        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

    can we use code like bellow?

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

Log in to reply

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