劍指offer：旋轉數組的最小值

題目描述
把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。 輸入一個非減排序的數組的一個旋轉，輸出旋轉數組的最小元素。 例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 NOTE：給出的所有元素都大于0，若數組大小為0，請返回0。

class Solution:
    """
    由于整個數組在一定程度上是有序的，因此可以借鑒二分查找的思想，達到接近O(logn)的時間復雜度。
    將一個有序(升序)數組的前x個元素挪到末尾，這里可以分類進行討論。

    第一類：挪動元素個數為數組長度的整數倍，那么這時候等于沒有挪動，最小值出現在idx=0
    第二類：挪動元素個數不是數組長度的整數倍，那么這時候挪動后的數組可以分成兩個子數組，其中左邊子
          數組的元素都是大于等于右邊子數組的。
          [3, 4, 5, 1, 2]
          這時候我們維護兩個指針p1和p2，分別指向左邊子數組和右邊子數組。當中間元素大于等于p1指向
          的元素的時候，則中間元素屬于左邊子數組，反之屬于右邊子數組。
          當兩個指針相鄰的時候p2就指向了右邊子數組的第一個元素，也就是整個數組的最小值。
    第三類：[1, 0, 1, 1, 1]
          當p1和p2指向的元素和中間的元素相等的時候，這時候如果按照第二類的思路，那么會誤判最小值
          在中間元素之后，因此這種情況下我們需要順序查找。
    """
    def minNumberInRotateArray(self, rotateArray):
        if not rotateArray:
            return 0

        # 將mid初始化為0，可以處理第一類情況，因為這時不會進入循環，直接輸出最小值
        left, mid, right = 0, 0, len(rotateArray) - 1

        while rotateArray[left] >= rotateArray[right]:
            # 如果left和right已經相鄰，那么最小值就是right指向的元素
            if left == right - 1:
                mid = right
                break

            mid = (left + right) >> 1
            # 如果left, right, mid指向的元素都相等，那么需要對這個區間進行順序查找，否則按照
            # 第二類情況的解題思路會判斷錯誤
            if rotateArray[left] == rotateArray[mid] == rotateArray[right]:
                return min(rotateArray[left:right + 1])

            # 中間元素在左半邊，最小值出現在右邊子數組[mid, right]
            if rotateArray[left] <= rotateArray[mid]:
                left = mid
            # 中間元素在右半邊，最小值出現在左邊子數組[left, mid]
            else:
                right = mid

        return rotateArray[mid]