旋转有序数组

旋转有序数组：ll = [15,16,19,20,25,1,3,4,5,7,10,14]
使用二分查找，分三种情况处理

list[m] == item   return
list[m] <= list[right] 右侧有序,如果alist[m]<item <= alist[right],则left=m+1,else right = m-1
list[m]>list[left] 左侧有序,如果alist[left]<= item < alist[m],则right = m-1,else left = m+1

代码如下

# 旋转有序数组
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)