二分查找

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

中心结论：维护候选区间 [lo,hi];每步取 mid 比较,丢弃一定不含答案的一半。

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

你可以假设 nums 中的所有元素是不重复的。 n 将在 [1, 10000]之间。 nums 的每个元素都将在 [-9999, 9999]之间。

在本站主例中，在升序数组 [-1,0,3,5,9,12] 中查找 target=9 的下标。

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

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

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

1. 1建模把输入翻译成“有序区间闸门”，明确答案需要观察什么。
2. 2状态只维护 候选区间下界 lo、上界 hi、中点 mid。
3. 3转移每一步按照 维护候选区间 [lo,hi];每步取 mid 比较,丢弃一定不含答案的一半。
4. 4收尾读取 在下标 4 处找到 9。，并复核边界与复杂度。

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

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

给出一个数组，要求在数组中搜索等于 target 的元素的下标。如果找到就输出下标，如果找不到输出 -1 。 简单题，二分搜索的裸题。

维护候选区间 [lo,hi];每步取 mid 比较,丢弃一定不含答案的一半。

执行过程中持续维护：候选区间下界 lo、上界 hi、中点 mid。

正确性依赖以下不变量：答案若存在,一定落在当前候选区间 [lo, hi] 内。

面试时可以压缩为：数组有序,我维护候选区间 [lo,hi],每步取 mid:相等即返回,a[mid] 偏小则 lo=mid+1,偏大则 hi=mid-1;每步砍半,O(log n)。

落到当前题，执行机制可以压缩为：维护候选区间 [lo,hi];每步取 mid 比较,丢弃一定不含答案的一半。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入在升序数组 [-1,0,3,5,9,12] 中查找 target=9 的下标。 因为：维护候选区间 [lo,hi];每步取 mid 比较,丢弃一定不含答案的一半。
2. 2候选区间 = 整个数组把整个有序数组作为初始候选区间。 因为：数组有序是二分的前提:看一眼 mid 就能判断答案在左还是右。
3. 3看 mid=2,a[mid]=3取区间中点 mid,比较 a[mid] 与 target。 因为：a[mid] 偏小,答案只可能在右半。
4. 4丢弃左半,lo = mid+1把 mid 及其左侧全部排除。 因为：有序数组里 mid 左侧都 ≤ a[mid] < target,不可能是答案。
5. 5预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
6. 6看 mid=4,a[mid]=9取区间中点 mid,比较 a[mid] 与 target。 因为：正好相等,mid 就是答案。
7. 7命中,返回下标 4a[mid] 等于 target,直接返回下标。 因为：二分每一步都不丢弃可能含答案的一侧,命中即正确。
8. 8收尾与复杂度在下标 4 处找到 9。 因为：时间 O(log n) · 空间 O(1)。维护候选区间 [lo,hi];每步取 mid 比较,丢弃一定不含答案的一半。

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

func search(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)>>1
		if nums[mid] == target {
			return mid
		} else if nums[mid] > target {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return -1
}

func main() {
    // 1. 主例
    //    输入：mode="classic", array=[-1,0,3,5,9,12], target=9
    //    期望：在下标 4 处找到 9。
    //
    // 2. 失败 / 未命中
    //    检查：mid 比较后要写 mid±1,否则区间不缩小会死循环。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC35 搜索插入位置；LC33 旋转有序数组搜索
}

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

1. 1题意在升序数组 [-1,0,3,5,9,12] 中查找 target=9 的下标。
2. 2重复线性扫描没有利用判定条件的单调性；二分每次用一个判断安全排除一半候选。
3. 3优化维护候选区间 [lo,hi];每步取 mid 比较,丢弃一定不含答案的一半。
4. 4证明答案若存在,一定落在当前候选区间 [lo, hi] 内。
5. 5复杂度时间 O(log n)，空间 O(1)