把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

示例1

• 输入：numbers = [3,4,5,1,2]

• 输出：1

示例2

• 输入：numbers = [2,2,2,0,1]

• 输出：0

提示

• n == numbers.length

• 1 <= n <= 5000

• -5000 <= numbers[i] <= 5000

• numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

算法：二分法

首先，从审题中我们了解到，

• 条件一：“原来是一个升序排列的数组”，说明他是一个有顺序的数组，即左边的数小于等于右边的数。

• 条件二：“把最开始的若干个元素搬到数组末尾”，说明最小数字是在数组中，可以把旋转后的数组理解为“两个有序的数组”。

因为数组是“可能存在重复”的，所以有两种情况“不重复数组”和“重复数组”。

场景一：不重复数组

原数组：[1,2,3,4,5]，经过一次旋转变为：[3,4,5,1,2]。

首先我们取中间值 “5” 跟最右侧的 “2” 比较，发现 5 > 2 ，说明数组中的最小值在中间值 “5” 的右侧，然后我们右侧值取 “1” 跟中间值侧的 “5” 比较，发现 1 < 5，即该值为最小值。

场景二：重复数组

原数组：[0,1,2,2,2]，经过一次旋转变为：[2,2,2,0,1]。

首先我们取中间值 “2” 跟最右侧的 “1” 比较，发现 2 > 1，说明数组中的最小值在中间值 “2” 的右侧，然后我们右侧值取 “0” 跟中间值侧的 “2” 比较，发现 0 < 2，即该值为最小值。

代码如下：

复杂度分析

• 时间复杂度 ：log以2为底n的对数， 在特例情况下（例如 [1, 1, 1, 1]），会退化到 O(N)。

• 空间复杂度 ：O(1)， low , high , pivot 变量使用常数大小的额外空间。

END

本文内容出处是力扣官网，希望和大家一起刷算法，在后面的路上不变秃但是变强！

好兄弟可以点赞并关注我的公众号“javaAnswer”，全部都是干货。