Go sort.Search 面对重复值时怎么找到第一个插入位置

平时写Go代码处理有序切片的时候，不少人用`sort.Search`碰到重复元素就懵了，不知道怎么拿到最左侧的第一个插入位置，怕返回的下标不准，插入之后会打乱原有排序的稳定性。

只要你的入参切片是升序排列，且传给`sort.Search`的判断条件写的是「当前下标的元素 >= 待插入的目标值」，它返回的结果天然就是第一个符合要求的插入位置，完全不需要额外遍历找偏移。

在升序切片里插入一个可能已经出现多次的值，真正需要的通常不是“找到某个相等元素”，而是找到第一个大于等于目标值的位置。Go 的 sort.Search 正好适合这个问题：把判断条件写成 data[i] >= target，它会返回第一个满足条件的下标，也就是常说的 lower-bound。

直接结论：对升序数据调用 sort.Search(len(data), func(i int) bool { return data[i] >= target })。当切片是 []int{1, 3, 5, 5, 8}、目标值是 5 时，结果是第一个 5 的下标，而不是后面的重复项；如果目标值大于所有元素，返回值就是 len(data)，可以直接作为追加位置。

官方文档：https://pkg.go.dev/sort#Search

先把问题改写成单调谓词

sort.Search 不接收“目标值”和“比较函数”两个独立参数，它只关心一个从 false 变成 true 后不再回退的谓词。升序切片里使用 data[i] >= target 时，小于目标值的前缀都是 false，从第一个满足条件的位置开始都是 true。重复值不会破坏这个分界，反而会让“第一个 true”成为稳定的插入位置。

用 sort.Search 找到重复值的第一个位置

下面的函数只返回插入下标，不修改原切片。它把目标值捕获到谓词中，并把 Search 的结果原样交给调用方。因为下标可能等于切片长度，所以不能无条件读取 data[i]。

package main

import "sort"

// lowerBound 返回升序 data 中第一个大于等于 target 的下标。
func lowerBound(data []int, target int) int {
	// 谓词必须保持单调：前面为 false，后面只能为 true。
	return sort.Search(len(data), func(i int) bool {
		return data[i] >= target
	})
}

例如 data := []int{1, 3, 5, 5, 8} 时，目标值 5 的结果是 2。下标 3 也指向 5，但它不是第一个满足条件的位置，因此不会被返回。目标值 6 时结果是 4，目标值 10 时结果是 5，也就是 len(data)。

命中、重复和末尾插入要分开判断

sort.Search 找到的是边界，不承诺目标值一定存在。要判断是否命中，需要先确认下标没有越界，再比较当前位置的值。这个判断也能区分“插入到某个重复值前面”和“目标值不在切片里”。

func locate(data []int, target int) (index int, found bool) {
	// 先找第一个可能的位置；找不到时 index 会等于 len(data)。
	index = sort.Search(len(data), func(i int) bool {
		return data[i] >= target
	})

	// 只有下标仍在切片内且值相等，才算真正命中。
	if index 

空切片也是同一套规则：sort.Search(0, ...) 返回 0，它既是 len(data)，也是新元素应该插入的位置。不要把返回值和 -1 比较，sort.Search 的未命中约定是返回搜索范围的右端点。

封装插入函数并保持原有顺序

如果需求是把新值放入有序切片，可以复用 lower-bound。对于重复值，这个实现会把新值放在已有重复值之前；如果业务希望放在重复值之后，那是 upper-bound 的另一个问题，谓词需要改成严格大于。

func insertSorted(data []int, target int) []int {
	// lower-bound 让相同值的新元素落在已有重复值之前。
	index := sort.Search(len(data), func(i int) bool {
		return data[i] >= target
	})

	// 扩容后向右移动尾部元素，为新值腾出一个位置。
	data = append(data, 0)
	copy(data[index+1:], data[index:])
	data[index] = target
	return data
}

这里的 append 可能复用原底层数组，也可能分配新数组；调用方应按返回值接住结果。若切片容量足够，copy 会把从 index 开始的尾部元素整体右移一格；当 index == len(data) 时，尾部为空，代码自然退化成追加。

最容易出错的三个边界

• 谓词不单调：例如在升序切片中混用 >、 或额外的奇偶判断，可能让结果失去含义。先确认数据顺序和谓词方向。
• 忘记检查 len(data)：未命中时返回的是末尾位置，直接访问 data[index] 会越界。
• 把 lower-bound 当成最后一个重复值：第一个大于等于目标值对应“重复值之前”；要找重复值之后的边界，需要另写严格大于的谓词。

几个容易混淆的问题

为什么重复值不会随机返回某一个下标？

因为 sort.Search 的契约是返回范围内第一个使谓词为真的位置。只要谓词是 data[i] >= target，第一个重复值自然就是边界。

返回 len(data) 是错误吗？

不是。它表示所有元素都小于目标值，目标应该插到末尾。只有在要读取 data[index] 时，才需要先检查下标是否小于切片长度。

怎样把新值放到重复值之后？

把谓词改成 data[i] > target，找到第一个严格大于目标值的位置，再把新值插入那里。这是 upper-bound 语义，和本文的“第一个插入位置”不同。

处理重复值时，可以把 sort.Search 记成一句话：在升序数据中用 data[i] >= target 找到第一个 true，再根据是否等于 len(data) 和当前位置是否等于目标值，分别处理插入与命中。这样二分查找的边界、重复值的策略和切片移动的责任都清楚分开。