11. 旋转数组的最小数字.md

解题思路

数组中找最小值，使用 O(n) 时间复杂度的算法没什么好说的 题干给的是一个有序的数组，所以可以使用性能更优的二分查找来做

1. 二分查找

只有中点和右端点比较大小，才能确定哪边属于连续递增数组 存在三种情况：

1. 中间值比最右值大，最小元素肯定出现在右半部分，且肯定不是中间值 [3,4,5,1,2]
2. 中间值比最右值小，最小元素肯定出现在左半部分，且可能是中间值 [1,2,3,4,5]
3. 中间值和最右值相等，可能是 [1,1,1,2,1]，也可能是 [1,1,1,0,1]，所以只有缩小范围再试试

func minArray(nums []int) int {
    l, r := 0, len(nums)-1
    for l < r {
        mid := l + (r-l) >> 1
        if nums[mid] > nums[r] {
            l = mid+1
        } else if nums[mid] < nums[r] {
            r = mid
        } else {
            r--
        }
    }
    return nums[l]
}