题目

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

题解

对于旋转数组[3, 4, 5, 1, 2]

可以从旋转点划分为两个排序数组

由于左排序数组的任一元素都 >= 右排序数组，可以以此作为判断条件进行二分查找

初始：left = 0，right = len(nums) - 1，mid = (left + right) / 2

循环执行：

nums[mid] > nums[right]：mid位于左排序数组中，旋转点位于[mid + 1，right]

nums[mid] < nums[right]：mid位于右排序数组中，旋转点位于[left，mid - 1]

nums[mid] = nums[right]：当旋转数组中存在重复元素，且重复元素分别位于左右两个排序数组，此时无法直接判定mid位于哪个排序数组；由于nums[right]为重复元素，因此旋转点必然位于[left，right - 1]，执行right -= 1

left = right时，结束循环，nums[left]即为结果

初始：

第一次循环：nums[mid] > nums[right]，left = mid + 1

第二次循环：nums[mid] = nums[right]，right -= 1

第三次循环：nums[mid] < nums[right]，right = mid - 1

第四次循环：此时已不能满足条件left < right，循环结束，nums[left]即为结果

代码

func minArray(numbers []int) int {
	var left, right int = 0, len(numbers) - 1
	for left < right {
		mid := (left + right) / 2
		if numbers[mid] < numbers[right] {
			right = mid
		} else if numbers[mid] > numbers[right] {
			left = mid + 1
		} else {
			right--
		}
	}
	return numbers[left]
}