Python binary search solution with detailed comment


  • 0
    G
    class Solution(object):
        def search(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            left,right=0,len(nums)-1
            while left<=right:
                mid=(left+right)//2
                if nums[mid]==target:
                    return mid
                elif nums[mid]>target:
                    if target<nums[left]<=nums[mid]:left=mid+1
                    else:right=mid-1
                else:
                    if nums[mid]<=nums[right]<target:right=mid-1
                    else:left=mid+1
            return -1
    

    Basic idea is binary search, but compared with ordinary binary search, we should do some revisions. Because for example , when nums[mid]>target, target may not be in the range left~mid-1, because the array is rotated ,and the only exception here is : target<nums[left], (I write taget <nums[left]<=nums[mid] in the code, though)


Log in to reply
 

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