旋轉(zhuǎn)有序數(shù)組：ll = [15,16,19,20,25,1,3,4,5,7,10,14]
使用二分查找，分三種情況處理
list[m] == item return
list[m] <= list[right] 右側(cè)有序,如果alist[m]<item <= alist[right],則left=m+1,else right = m-1
list[m]>list[left] 左側(cè)有序,如果alist[left]<= item < alist[m],則right = m-1,else left = m+1
代碼如下
# 旋轉(zhuǎn)有序數(shù)組
ll = [15,16,19,20,25,1,3,4,5,7,10,14]
class Solution(object):
def func(self, alist, item):
n = len(alist)
found = False
index = -1
left = 0
right = n-1
while left <= right and not found:
m = (left + right) // 2
if item == alist[m]:
found = True
index = m
elif alist[m] <= alist[right]:
if alist[m] < item and item <= alist[right]:
left = m + 1
else:
right = m - 1
else:
if alist[left] <= item and item < alist[m]:
right = m - 1
else:
left = m + 1
return index
s = Solution()
s.func(ll, 15)
