leetcode33. 搜索旋转排序数组

搜索旋转排序数组

#python3
class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right =  len(nums)-1

        # 先找到最小数的位置
        # 左大右小
        while left<right:
            mid = (left+right)//2
            if nums[mid]>nums[right]: left=mid+1
            else:right=mid
        root = right  # 此时right = left

        left = 0
        right =  len(nums)-1
        while left<=right:
            mid = (left+right)//2
            realmid = (mid+root)%len(nums)
            if nums[realmid]==target:return realmid
            if nums[realmid]<target:left=mid+1
            else:right=mid-1
        return -1