搜索旋转排序数组
#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
