LC35：找 target 应该站在哪条缝里

怎样从“nums = [1, 3, 5, 6]，target = 2。要找 target 应插入哪条缝，数组才继续有序。”推导出 二分查找 · lower_bound，并证明每次状态变化都不会漏掉答案？

中心结论：在有序数组中，LC35 真正要找的是 target 应该插入的那条缝。换成条件就是找第一个 >= target 的下标：左边都 < target，右边都 >= target，答案就是中间那条分界线。

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

在本站主例中，在升序数组 [1,3,5,6] 中找 target=5 应插入的位置。

算法最终需要得到或观察：5 应插入在下标 2。

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

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

1. 1建模把输入翻译成“有序区间闸门”，明确答案需要观察什么。
2. 2状态只维护 半开区间 [lo, hi)，lo/hi 是两扇闸门，mid 是扫描探针，hi 初始为 len(nums)。
3. 3转移每一步按照 在有序数组中，LC35 真正要找的是 target 应该插入的那条缝。换成条件就是找第一个 >= target 的下标：左边都 < target，右边都 >= target，答案就是中间那条分界线。
4. 4收尾读取 target=2 插在 1 和 3 中间，返回 index=1。，并复核边界与复杂度。

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

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：半开区间 [lo, hi)，lo/hi 是两扇闸门，mid 是扫描探针，hi 初始为 len(nums)。

给出一个已经从小到大排序后的数组，要求在数组中找到插入 target 元素的位置。 这一题是经典的二分搜索的变种题，在有序数组中找到最后一个比 target 小的元素。

搜索插入位置等价于求「第一个 ≥ target 的下标」,即下界二分;a[mid]≥target 时 hi=mid 保留 mid。

执行过程中持续维护：候选区间 [lo,hi](hi 初值取 n)、中点 mid。

正确性依赖以下不变量：收敛时 lo 左边都 < target、lo 及右边都 ≥ target。

面试时可以压缩为：搜索插入位置就是求第一个 ≥ target 的下标,我用下界二分:a[mid]≥target 时 hi=mid(保留 mid),否则 lo=mid+1;收敛后 lo 即答案,O(log n)。

落到当前题，执行机制可以压缩为：在有序数组中，LC35 真正要找的是 target 应该插入的那条缝。换成条件就是找第一个 >= target 的下标：左边都 < target，右边都 >= target，答案就是中间那条分界线。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目输入输入是一排升序货架格子：[1,3,5,6]，待插入芯片 target=2。 因为：在有序数组中，LC35 真正要找的是 target 应该插入的那条缝。换成条件就是找第一个 >= target 的下标：左边都 < target，右边都 >= target，答案就是中间那条分界线。
2. 2分界线模型target=2 应该插在 1 和 3 中间，插入后数组仍然有序。 因为：一旦找到第一个 >= target 的下标，target 放在这里不会破坏有序性。
3. 3初始化 [0, n)候选插槽从 0 到 4：包括数组最左边，也包括最后一个元素右侧。 因为：半开区间 [lo,hi) 让 hi 可以安全取 n，表示答案可能在数组末尾。
4. 4mid=2, nums[2]=5当前区间 [0,4)，mid=2，nums[2]=5。 因为：找第一个 >= target 时，满足条件的 mid 可能就是最左答案，只能收右边界。
5. 5mid=1, nums[1]=3当前区间 [0,2)，mid=1，nums[1]=3。 因为：3 已经满足 >= target，但第一个满足的位置可能还在左侧。
6. 6mid=0, nums[0]=1当前区间 [0,1)，mid=0，nums[0]=1。 因为：有序数组里 index 0 及左边都 <=1<2，不可能成为第一个 >=2 的位置。
7. 7return lo两个闸门合拢在 1 和 3 中间，target 芯片落入 index=1 的插槽。 因为：循环结束时候选分界线只剩一个位置，lo 就是第一个 >= target 的下标。

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

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

func main() {
    // 1. 主例
    //    输入：mode="lower-bound", array=[1,3,5,6], target=5
    //    期望：5 应插入在下标 2。
    //
    // 2. 失败 / 未命中
    //    检查：下界二分用 hi=mid(不是 mid-1),否则会跳过答案。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC704 二分查找；LC34 查找首尾位置
}

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

1. 1题意nums = [1, 3, 5, 6]，target = 2。要找 target 应插入哪条缝，数组才继续有序。
2. 2重复线性扫描没有利用判定条件的单调性；二分每次用一个判断安全排除一半候选。
3. 3优化在有序数组中，LC35 真正要找的是 target 应该插入的那条缝。换成条件就是找第一个 >= target 的下标：左边都 < target，右边都 >= target，答案就是中间那条分界线。
4. 4证明lo 左边的元素都 < target。hi 右边的元素都不是当前候选区。答案始终在 [lo, hi) 里面。
5. 5复杂度时间 O(log n)，空间 O(1)