假設(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) 級別讨跟。
示例 1:
輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出: 4
示例 2:
輸入: nums = [4,5,6,7,0,1,2], target = 3
輸出: -1
分析：看到對復(fù)雜度的要求纪他，首先想到二分法，經(jīng)過旋轉(zhuǎn)的序列晾匠，因此與我們之前所想到的二分法應(yīng)該要有一些差異茶袒。分析數(shù)字特征明顯看出，整個(gè)數(shù)據(jù)變成兩個(gè)部分凉馆，前邊是較大的數(shù)薪寓，從小到大，后邊是較小的數(shù)澜共，從大到小排列向叉，找出中間點(diǎn)處于那一段，跟每一段的端點(diǎn)比較嗦董。
- 首先找到中間點(diǎn)位置i = （min+max）//2
- 判斷中間點(diǎn)值與target 大小
3a.如果中間點(diǎn)值比target小
判斷中間點(diǎn)處于大段還是小段母谎，如果中間點(diǎn)值小于數(shù)組中最后一個(gè)數(shù)，則中間點(diǎn)處于大段京革，此時(shí)小段最大數(shù)位于數(shù)組最后一個(gè)數(shù)奇唤，若小段最后一個(gè)數(shù)仍舊比target小，則丟棄小段數(shù)據(jù)匹摇，更新 max = i-1咬扇，相反情況則是丟棄大段數(shù)據(jù)更新min = i+1
3b.如果中間點(diǎn)值比target大
判斷中間點(diǎn)處于大段還是小段，如果中間點(diǎn)值大于數(shù)組中最后一個(gè)數(shù)廊勃，則中b間點(diǎn)處于大段冗栗，此時(shí)大段第一個(gè)數(shù)最小，若大段第一個(gè)數(shù)仍舊比目標(biāo)小供搀，丟棄大段數(shù)據(jù)，更新 min= i+1钠至，否則葛虐，max=i-1
def search(nums: List[int], target: int) -> int:
imin,imax = 0,len(nums)-1
while imin <= imax:
i = (imin+imax)//2
if nums[i]<target:#判斷i在小段還是大段
if nums[i] < nums[-1] and nums[-1]<target:
imax = i-1
else:
imin = i+1
elif nums[i] > target:
if nums[i]>nums[-1] and nums[0]>target:
imin = i+1
else:
imax = i-1
else:
return i
return -1
