思路

这个是 LeetCode: 153.Find Minimum in Rotated Sorted Array 扩展，增加了以下几种边界情况：

  • ‘[2, 2, 2, 2, 1]’
  • ‘[3, 1, 3]’
  • ‘[1, 1, 1]’
  • ‘[10, 1, 10, 10, 10]’

但核心依然是判断最小值是在左边还是右边。假设如下数组：

  • ‘[3, 3, 3, 1, 3]’

  • left[0]=3, right[4]=3, mid[2]=3, 这时候不确定最小值在哪边但是 right– 是安全的，所以执行 right–

  • left[0]=3, right[3]=1, mid[2]=3, 这时候 mid < right 说明最小值在 mid 的右边，所以调整 left = mid + 1

  • 左右两边索引一致终止循环

实现

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