题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

这一题最简单的解法是n复杂度，过一遍然后记录最小值就好了，但是两段有序数组这个信息没有用到，肯定有更好的解法。
因为是基本有序的，所以二分法可以考虑。
以下代码主要参考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点已经很大了，所以不可能是最小数字，在右边+1
            elif numbers[m] < numbers[j]:
                j = m        
            else:
                j -= 1    # 同样很关键
        return numbers[i]

总结

个人一开始想的方法是判断某个数两边的数都比它大，写出来的代码考虑很多边界情况，还不如直接记录最小值的办法。
来自leetcode题解，需要注意的点：

image.png

** 要跟右边比较！**
** 后面要 j-=1! **

温故知新

之前并没有完全理解原po的做法，自己动手写了一下，发现return的时候，返回的实际上是 left 而不是mid。
首先，算法的目的是通过缩小i j 之间的范围，最终i=j，找到最小的数字（右排数组的第一位）。
初始化时 i 不一定在左派数组中，j一定在右排数组中 -> 不能让中位数和左边比较。
值相等的时候，j -= 1