面试题11-easy. 旋转数组的最小数字

面试题11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [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

这个题最直观的解法就是直接暴力顺序遍历一遍数组就完了，但是这并不是最优解，我们可以使用二分法降低时间复杂度

这里比较推荐这个题解：面试题11. 旋转数组的最小数字（二分法，清晰图解）
排序数组的查找问题首先考虑使用 二分法 解决，其可将遍历法的 线性级别 时间复杂度降低至 对数级别

使用二分法的解法如下：

// 利用二分查找逼夹来找到数组中最小的点
func minArray(numbers []int) int {
    left,right := 0,len(numbers)-1

    for left < right{

        mid := left + (right-left)>>1 

        if numbers[mid]>numbers[right]{ //mid 取到了左侧数组中的数据，需要左侧边界需要右移
            left = mid+1
        }else if numbers[mid]<numbers[right]{ // mid 取到了右侧边界中的数据，右侧边界需要替换
            right = mid
            //right = mid-1 不这么写是因为 mid可能为旋点
        }else{
            right--
        }
    }
    return numbers[left]
}