package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
*/
func minNumberInRotateArray( nums []int ) int {
    // write code here
    // 二分法
    left, right := 0, len(nums)-1

    for left < right {
        mid := (right-left)/2 + left

        // “夹”的思想，我们知道位于后面的旋转数组部分一定是小于前面的部分的
        // 因此我们可以以最右侧元素作为基准，找到第一个比它小的元素，这时我们一直在往右边靠
        // 一旦找到说明我们已经进入了旋转数组部分，这时我们需要往左靠，即更新 right
        // 而如果我们找到的值 == right 处值，也是向左靠，只不过是移动一个位置
        // 最终以 left 值作为边界，满足条件的最左侧边界值。
        if nums[mid] > nums[right] {
            left = mid + 1
        } else if nums[mid] < nums[right] {
            right = mid
        } else {
            right--
        }
    }

    return nums[left]
}

如上图所示，原本位于开头的 [1, 2] 部分被搬移到了末尾，将原数组分割成两个非递减的数组。

为了方便，我们将 [1, 2] 称为迁移部分， [3, 4, 5] 称为未迁移部分，可得出如下结论：

  1. 未迁移部分元素值大于等于迁移部分元素值；
  2. 旋转数组的最小数字是迁移部分的最左侧元素的值；

我们根据上述两个结论，我们可以使用二分法找比迁移部分的最右侧元素小的元素值：

  1. 如果 mid 处的元素值大于迁移部分最右侧的元素值，那么说明 mid 处元素仍然位于未迁移部分，迁移部分一定在 mid 右侧，所以我们更新 left 指针；
  2. 如果 mid 处的元素小于迁移部分最右侧的元素值，那么说明 mid 处元素已经处于迁移部分中了（只有迁移部分元素才可能小于最右侧元素），这时候我们知道 mid 可能是迁移部分的最小数字，但也有可能在 [left, mid）之间，所以我们更新 right 指针。
  3. 如果 mid 处的元素等于迁移部分最右侧的元素值，那么我们唯一知道的是 right 处一定不可能是最小数字了（因为 mid 位于 right 左侧），所以我们将 right 减 1。至于为什么不让 right 直接更新为 mid，我们后面会有一个图示专门说明这种特殊情况。

我们举三个例子说明上述代码逻辑：

例 1

初始时，left = 0 ，right = 4 ；

mid = 2，arr[2] > arr[4] ，说明 mid 所指向的元素不在迁移部分，此时我们继续往右边找，更新 left = mid + 1 = 3；

mid = 3，arr[3] < arr[4] ，说明 mid 所指向的元素已经在迁移部分了，我们继续往左侧找左边界，right = mid = 3；

left = 3, right = 3, mid = 3 ，arr[3] = arr[3] , right = right - 1 = 2 ，循环结束，返回 left 指向的值，return 1。

例 2

例 3