題目

把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個遞增排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如，數(shù)組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。

示例 1：

輸入：[3,4,5,1,2]
輸出：1

示例 2：

輸入：[2,2,2,0,1]
輸出：0

注意：本題與主站 154 題相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法

這一題最簡單的解法是n復雜度，過一遍然后記錄最小值就好了，但是兩段有序數(shù)組這個信息沒有用到，肯定有更好的解法。
因為是基本有序的，所以二分法可以考慮。
以下代碼主要參考leetcode上的一個解法，分析也很好。

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        # 二分法
        i = 0
        j = len(numbers)-1
        while (i<j):
            m = (i+j)//2
            if numbers[m] > numbers[j]:    #
                i = m + 1  # m點已經(jīng)很大了，所以不可能是最小數(shù)字，在右邊+1
            elif numbers[m] < numbers[j]:
                j = m        
            else:
                j -= 1    # 同樣很關(guān)鍵
        return numbers[i]

總結(jié)

個人一開始想的方法是判斷某個數(shù)兩邊的數(shù)都比它大，寫出來的代碼考慮很多邊界情況，還不如直接記錄最小值的辦法。
來自leetcode題解，需要注意的點：

image.png

** 要跟右邊比較！**
** 后面要 j-=1! **

溫故知新

之前并沒有完全理解原po的做法，自己動手寫了一下，發(fā)現(xiàn)return的時候，返回的實際上是 left 而不是mid。
首先，算法的目的是通過縮小i j 之間的范圍，最終i=j，找到最小的數(shù)字（右排數(shù)組的第一位）。
初始化時 i 不一定在左派數(shù)組中，j一定在右排數(shù)組中 -> 不能讓中位數(shù)和左邊比較。
值相等的時候，j -= 1