11. 旋转数组的最小数字

1.利用二分法实现O(log n)的查找，但是要主要当index1 = index2 = midindex时，只能按顺序查找

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:return 0
        lenth = len(rotateArray)
        index1 = 0
        index2 = lenth - 1
        midindex = 0
        while rotateArray[index1] >= rotateArray[index2]:
            if index2 - index1 == 1:
                midindex = index2
                return rotateArray[midindex]
            midindex = (index1 + index2) // 2
            if rotateArray[index1] == rotateArray[index2] == rotateArray[midindex]:
                return self.MinOrder(rotateArray, index1, index2)
            if rotateArray[index1] <= rotateArray[midindex]:
                index1 = midindex
            elif rotateArray[index2] >= rotateArray[midindex]:
                index2 = midindex
        return rotateArray[midindex]
    def MinOrder(self, rotateArray, index1, index2):
        result = rotateArray[index1]
        for i in range(index1,index2,1):
            if rotateArray[i] < result:
                result = rotateArray[i]
        return result

2. mid指针值只和right指针指向的值比较大小

• 当 numbers[mid] < numbers[right]​ 时，说明最小值在 ​[left, mid]​ 区间中，则令 right = mid，用于下一轮计算
• 当 numbers[mid] > numbers[right]​ 时，说明最小值在 [mid, right]​ 区间中，则令 left = mid + 1，用于下一轮计算
• 当 numbers[mid] == numbers[right]​ 时，无法判断最小值在哪个区间之中，此时让 right--，缩小区间范围，在下一轮进行判断

链接：https://leetcode-cn.com/leetbook/read/illustrate-lcof/55deoi/

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        if not numbers:
            return None
        s = 0
        e = len(numbers)-1
        while s<e: 
            mid = (s+e)//2
            if numbers[mid] > numbers[e]:
                s = mid+1
            elif numbers[mid] < numbers[e]:
                e = mid
            else:
                e = e-1
        return numbers[s]