搜索旋转排序数组

怎样从“在旋转升序数组 [4,5,6,7,0,1,2] 中查找 target=0 的下标。”推导出 二分查找 · 旋转，并证明每次状态变化都不会漏掉答案？

中心结论：取 mid 后,[lo,mid] 与 [mid,hi] 至少有一半是有序的;在有序那半判断 target 是否落入,据此决定去哪半。

假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

在本站主例中，在旋转升序数组 [4,5,6,7,0,1,2] 中查找 target=0 的下标。

算法最终需要得到或观察：在下标 4 处找到 0。

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

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

1. 1建模把输入翻译成“有序区间闸门”，明确答案需要观察什么。
2. 2状态只维护 候选区间 [lo,hi]、中点 mid、哪一半有序。
3. 3转移每一步按照 取 mid 后,[lo,mid] 与 [mid,hi] 至少有一半是有序的;在有序那半判断 target 是否落入,据此决定去哪半。
4. 4收尾读取 在下标 4 处找到 0。，并复核边界与复杂度。

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

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：候选区间 [lo,hi]、中点 mid、哪一半有序。

给出一个数组，数组中本来是从小到大排列的，并且数组中没有重复数字。但是现在把后面随机一段有序的放到数组前面，这样形成了前后两端有序的子序列。在这样的一个数组里面查找一个数，设计一个 O(log n) 的算法。如果找到就输出数组的小标，如果没有找到，就输出 -1 。 由于数组基本有序，虽然中间有一个“断开点”，还是可以使用二分搜索的算法来实现。现在数组前面一段是数值比较大的数，后面一段是数值偏小的数。如果 mid 落在了前一段数值比较大的区间内了，那么一定有 `nums[mid] > nums[low]`，如果是落在后面一段数值比较小的区间内，`nums[mid] ≤ nums[low]` 。如果 mid 落在了后一段数值比较小的区间内了，那么一定有 `nums[mid] < nums[high]`，如果是落在前面一段数值比较大的区间内，`nums[mid] ≤ nums[high]` 。还有 `nums[low] == nums[mid]` 和 `nums[high] == nums[mid]` 的情况，单独处理即可。最后找到则输出 mid，没有找到则输出 -1 。

取 mid 后,[lo,mid] 与 [mid,hi] 至少有一半是有序的;在有序那半判断 target 是否落入,据此决定去哪半。

执行过程中持续维护：候选区间 [lo,hi]、中点 mid、哪一半有序。

正确性依赖以下不变量：任意 mid 处,左右两段里至少一段是完全有序的。

面试时可以压缩为：旋转数组取 mid 后必有一半有序:先判断哪半有序,再看 target 是否落在那半的范围内,落入就去那半、否则去另一半;每步砍半,O(log n)。

落到当前题，执行机制可以压缩为：取 mid 后,[lo,mid] 与 [mid,hi] 至少有一半是有序的;在有序那半判断 target 是否落入,据此决定去哪半。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入在旋转升序数组 [4,5,6,7,0,1,2] 中查找 target=0 的下标。 因为：取 mid 后,[lo,mid] 与 [mid,hi] 至少有一半是有序的;在有序那半判断 target 是否落入,据此决定去哪半。
2. 2旋转有序数组,候选区间 = 全数组数组整体被旋转,不再全局有序。 因为：关键观察:取 mid 后,[lo,mid] 与 [mid,hi] 里至少有一半是有序的。
3. 3去右半,lo = mid+1把 mid 及左侧排除。 因为：已确认 target 只可能在右半区间内。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5mid=5:左半有序先判断哪一半是有序的,再看 target 是否落在那一半。 因为：只有在「有序的那一半」里才能用普通范围判断;落在其中就保留它,否则去另一半。
6. 6去左半,hi = mid-1把 mid 及右侧排除。 因为：已确认 target 只可能在左半区间内。
7. 7返回下标 4返回命中下标。 因为：每一步都只排除确定不含答案的一侧。
8. 8收尾与复杂度在下标 4 处找到 0。 因为：时间 O(log n) · 空间 O(1)。取 mid 后,[lo,mid] 与 [mid,hi] 至少有一半是有序的;在有序那半判断 target 是否落入,据此决定去哪半。

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

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

func main() {
    // 1. 主例
    //    输入：mode="rotated", array=[4,5,6,7,0,1,2], target=0
    //    期望：在下标 4 处找到 0。
    //
    // 2. 失败 / 未命中
    //    检查：只在「有序的那一半」里做范围判断,否则边界会判错。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC704 二分查找；LC153 寻找旋转排序数组最小值
}

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

1. 1题意在旋转升序数组 [4,5,6,7,0,1,2] 中查找 target=0 的下标。
2. 2重复线性扫描没有利用判定条件的单调性；二分每次用一个判断安全排除一半候选。
3. 3优化取 mid 后,[lo,mid] 与 [mid,hi] 至少有一半是有序的;在有序那半判断 target 是否落入,据此决定去哪半。
4. 4证明任意 mid 处,左右两段里至少一段是完全有序的。
5. 5复杂度时间 O(log n)，空间 O(1)