假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)咱娶。
( 例如彩倚，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )堵未。
搜索一個(gè)給定的目標(biāo)值，如果數(shù)組中存在這個(gè)目標(biāo)值赂苗，則返回它的索引愉耙，否則返回 -1 。
你可以假設(shè)數(shù)組中不存在重復(fù)的元素拌滋。
你的算法時(shí)間復(fù)雜度必須是 O(log n) 級(jí)別朴沿。
輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出: 4
題解：先判斷mid在左邊還是右邊，然后再判斷target是否在升序一邊败砂。
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] >= nums[left]:
if nums[left] <= target and target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
