题目描述#

给定一个原本按升序排列、且元素互不相同的数组 nums。数组经过若干次旋转后，顺序可能变成类似 [4,5,6,7,0,1,2] 这样的样子。

现在需要找出并返回数组中的最小元素，并且要求时间复杂度为 O(log n)。哎呀，旋转数组又来啦，这次咱不找某个目标值，而是找那个“断开后重新开始”的最小点～

看看看看，数组转了一圈，最小值就藏在那条“断崖”后面～

思路#

这题的核心观察是：拿数组最后一个元素 nums[last] 当参照物时，旋转数组会被分成两段。最小值左边那一段都比 nums[last] 大；最小值以及它右边的元素，都小于等于 nums[last]。

比如 [4,5,6,7,0,1,2]，最后一个元素是 2。前半段 4,5,6,7 都大于 2，说明它们还在最小值左边；后半段 0,1,2 都小于等于 2，说明最小值就在这段里。没错没错，咱要找的就是第一个 <= nums[last] 的位置。

二分时维护 [left, right]，但循环条件用 left < right，因为最终要把区间收缩到一个位置。如果 nums[mid] > nums[last]，说明 mid 还在左边那段，最小值一定在 mid 右侧，所以 left = mid + 1。否则 nums[mid] <= nums[last]，说明 mid 已经落在最小值所在的右段，答案可能就是 mid，所以不能跳过它，只能让 right = mid。

当 left == right 时，候选区间只剩一个位置，它就是最小值下标。照片当然不是现实，但如果把“比最后一个元素大还是小”这条分界拍清楚，旋转后的数组也会乖乖露出答案啦。好啦，三、二、一，咔嚓！

思维边界#

• 元素互不相同：不会出现大量重复值干扰二分判断，因此可以稳定地用 nums[mid] > nums[last] 区分左右两段。
• 固定参照物：last := right 保存的是原数组最后一个下标，后续 right 会变化，所以比较时要一直用 nums[last]。
• left < right：这种写法每轮都保留候选答案，最终让左右指针收缩到同一个最小值位置。
• right = mid：当 nums[mid] <= nums[last] 时，mid 可能就是最小值，不能写成 mid - 1。
• 未旋转情况：如果数组本身仍是升序，所有元素都 <= nums[last]，二分会一路把答案收缩到下标 0。

本姑娘小结：找第一个小于等于最后一个元素的位置，搞定搞定～

代码#

func findMin(nums []int) int {
    // 旋转数组中，最小值右边（包括自身）的所有元素都 <= 最后一个元素
    // 最小值左边的所有元素都 > 最后一个元素。
	left, right := 0, len(nums)-1
	last := right
	for left < right {
		mid := left + (right-left)/2
		if nums[mid] > nums[last] {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return nums[right]
}