旋转数组的最小数字

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray) == 0:
            return 0
        front = 0
        rear = len(rotateArray) - 1
        minVal = rotateArray[0]
        if rotateArray[front] < rotateArray[rear]:
            return rotateArray[front]
        else:
            while (rear - front) > 1:
                mid = (rear + front)//2
                if rotateArray[mid] > rotateArray[rear]:
                    front = mid
                elif rotateArray[mid] < rotateArray[front]:
                    rear = mid
                elif rotateArray[mid] == rotateArray[front] and rotateArray[front] == rotateArray[rear]:
                    for i in range(1, len(rotateArray)):
                        if rotateArray[i] < minVal:
                            minVal = rotateArray[i]
                            rear = i
            minVal = rotateArray[rear]
            return minVal

func minNumberInRotateArray(array []int) int {
    low, high := 0, len(array)-1
    if array[low] < array[high] {
        return array[low]
    }
    mid := (low + high) / 2
    for array[low] >= array[high] {
        // array[low] >= array[high] 所以此时high为最小值
        if high-low == 1 {
            mid = high
            break
        }
        mid = (low + high) / 2

        // array[low] array[mid] array[high]三者相等
        // 无法确定中间元素是属于前面还是后面的递增子数组
        // 只能顺序查找
        if array[low] == array[mid] && array[mid] == array[high] {
            return MinOrder(array, low, high)
        }


        if array[mid] >= array[low] {
            low = mid
        } else {
            high = mid
        }
    }
    return array[mid]
}

// 顺序查找
func MinOrder(array []int, low, high int) int {
    min := array[low]
    for i := low; i <= high; i++ {
        if array[i] < min {
            min = array[i]
        }
    }
    return min
}