寻找旋转排序数组中的最小值

怎样从“nums=[3,4,5,1,2],找旋转排序数组最小值。”推导出 二分查找 · 旋转最小，并证明每次状态变化都不会漏掉答案？

中心结论：旋转数组由两段递增区间组成,最小值是断点;比较 nums[mid] 与 nums[hi] 判断最小值在哪侧。

假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。请找出其中最小的元素。

你可以假设数组中不存在重复元素。

在本站主例中，nums=[3,4,5,1,2],找旋转排序数组最小值。

算法最终需要得到或观察：最小值 1 在下标 3。

线性扫描没有利用判定条件的单调性；二分每次用一个判断安全排除一半候选。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“有序区间闸门”，明确答案需要观察什么。
2. 2状态只维护 lo/hi/mid、nums[mid] vs nums[hi]。
3. 3转移每一步按照 旋转数组由两段递增区间组成,最小值是断点;比较 nums[mid] 与 nums[hi] 判断最小值在哪侧。
4. 4收尾读取 最小值 1 在下标 3。，并复核边界与复杂度。

二分的核心不是 mid 公式，而是左右哪一侧可以被证明不含答案。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：lo/hi/mid、nums[mid] vs nums[hi]。

给出一个原本从小到大排序过的数组，但是在某一个分割点上，把数组切分后的两部分对调位置，数值偏大的放到了数组的前部。求这个数组中最小的元素。 求数组最小的元素其实就是找分割点，前一个数比当前数大，后一个数比当前数也要大。可以用二分搜索查找，需要查找的两个有序区间。时间复杂度 O(log n)。这一题也可以用暴力解法，从头开始遍历，动态维护一个最小值即可，时间复杂度 O(n)。

旋转数组由两段递增区间组成,最小值是断点;比较 nums[mid] 与 nums[hi] 判断最小值在哪侧。

执行过程中持续维护：lo/hi/mid、nums[mid] vs nums[hi]。

正确性依赖以下不变量：最小值始终位于闭区间 [lo, hi] 中。；每次二分不是在找 target,而是在排除不可能包含最小值的一半区间。

面试时可以压缩为：我维护一个闭区间 [lo, hi],保证最小值一定在里面。每次取 mid,比较 nums[mid] 和 nums[hi]。如果 nums[mid] > nums[hi],说明 mid 位于左侧高值段,最小值在右侧,所以 lo = mid + 1;否则最小值在左侧并且 mid 可能就是答案,所以 hi = mid。循环结束时 lo == hi,返回 nums[lo]。时间复杂度 O(log n),空间 O(1)。

落到当前题，执行机制可以压缩为：旋转数组由两段递增区间组成,最小值是断点;比较 nums[mid] 与 nums[hi] 判断最小值在哪侧。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入nums=[3,4,5,1,2],找旋转排序数组最小值。 因为：旋转数组由两段递增区间组成,最小值是断点;比较 nums[mid] 与 nums[hi] 判断最小值在哪侧。
2. 2旋转数组 = 两段递增 + 断点旋转数组由两段递增区间组成,最小值位于断点。 因为：每次比较 nums[mid] 与 nums[hi],排除不可能含最小值的一半区间。
3. 3mid=2,比较 nums[mid]=5 与 nums[hi]=2取 mid 并与右端 hi 比较,判断 mid 落在哪一段。 因为：不是在找 target,而是在缩小仍含最小值的闭区间 [lo,hi]。
4. 4nums[mid] > nums[hi],最小值在右,lo = mid+1mid 位于左侧高值段,最小值在 mid 右侧。 因为：左半区间每个元素都不可能是全局最小值。
5. 5mid=3,比较 nums[mid]=1 与 nums[hi]=2取 mid 并与右端 hi 比较,判断 mid 落在哪一段。 因为：不是在找 target,而是在缩小仍含最小值的闭区间 [lo,hi]。
6. 6nums[mid] <= nums[hi],最小值在左含 mid,hi = midmid 可能就是最小值,只能收缩右边界到 mid。 因为：不能写 hi = mid - 1,否则会丢掉 mid 这个候选。
7. 7lo == hi == 3,返回 nums[lo]=1循环结束,lo 与 hi 重合于最小值下标。 因为：不变量保证最小值始终在 [lo,hi] 中,收敛即答案。
8. 8收尾与复杂度最小值 1 在下标 3。 因为：时间 O(log n) · 空间 O(1)。旋转数组由两段递增区间组成,最小值是断点;比较 nums[mid] 与 nums[hi] 判断最小值在哪侧。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一 二分
func findMin(nums []int) int {
	low, high := 0, len(nums)-1
	for low < high {
		if nums[low] < nums[high] {
			return nums[low]
		}
		mid := low + (high-low)>>1
		if nums[mid] >= nums[low] {
			low = mid + 1
		} else {
			high = mid
		}
	}
	return nums[low]
}

// 解法二 二分
func findMin1(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	if nums[len(nums)-1] > nums[0] {
		return nums[0]
	}
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)>>1
		if nums[low] < nums[high] {
			return nums[low]
		}
		if (mid == len(nums)-1 && nums[mid-1] > nums[mid]) || (mid < len(nums)-1 && mid > 0 && nums[mid-1] > nums[mid] && nums[mid] < nums[mid+1]) {
			return nums[mid]
		}
		if nums[mid] > nums[low] && nums[low] > nums[high] { // mid 在数值大的一部分区间里
			low = mid + 1
		} else if nums[mid] < nums[low] && nums[low] > nums[high] { // mid 在数值小的一部分区间里
			high = mid - 1
		} else {
			if nums[low] == nums[mid] {
				low++
			}
			if nums[high] == nums[mid] {
				high--
			}
		}
	}
	return -1
}

// 解法三 暴力
func findMin2(nums []int) int {
	min := nums[0]
	for _, num := range nums[1:] {
		if min > num {
			min = num
		}
	}
	return min
}

func main() {
    // 1. 主例
    //    输入：mode="rotated-min", array=[3,4,5,1,2], target=0
    //    期望：最小值 1 在下标 3。
    //
    // 2. 失败 / 未命中
    //    检查：错误 1:把 hi = mid 写成 hi = mid - 1 —— 当 nums[mid] <= nums[hi] 时,mid 可能就是最小值,不能丢掉。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC33 搜索旋转；LC162 峰值
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意nums=[3,4,5,1,2],找旋转排序数组最小值。
2. 2重复线性扫描没有利用判定条件的单调性；二分每次用一个判断安全排除一半候选。
3. 3优化旋转数组由两段递增区间组成,最小值是断点;比较 nums[mid] 与 nums[hi] 判断最小值在哪侧。
4. 4证明最小值始终位于闭区间 [lo, hi] 中。；每次二分不是在找 target,而是在排除不可能包含最小值的一半区间。
5. 5复杂度时间 O(log n)，空间 O(1)