Go sort.Find 怎样返回有序切片的插入位置

如果你需要在一个已经按升序排列的切片中查找目标，并且在找不到时知道它应该插在哪里，Go 的 sort.Find 可以一次返回两个结果：下标 i 和命中标记 found。关键是让 cmp(i) 按“目标值与第 i 个元素的比较结果”返回正数、零或负数，满足二分查找的单调关系。

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

found=true 时，i 是目标值的最小匹配下标；found=false 时，i 是第一个不大于目标比较结果的位置，也就是保持当前排序所需的插入下标。

先明确查找结果需要什么

常见的二分查找只关心“有没有”或者只返回一个位置，但业务代码往往还要区分两种情况：目标已经存在时读取原元素，目标不存在时把新元素插到正确位置。若先查位置、再单独比较一次，就会把边界判断拆散。

sort.Find 的签名是 Find(n int, cmp func(int) int) (i int, found bool)。它返回范围 [0,n) 内最小的、满足 cmp(i) 的下标；当这个下标的比较结果正好为零时，found 才是 true。如果所有元素都排在目标之前，返回的 i 就是 n。

用 cmp(i) 描述有序关系

最容易出错的地方不是调用函数，而是比较器方向。对于升序切片，推荐把目标值放在比较左侧：目标小于当前元素返回负数，目标等于当前元素返回零，目标大于当前元素返回正数。这样切片会呈现“前面是正数，中间可能是零，后面是负数”的形状。

package main

import (
	"fmt"
	"sort"
	"strings"
)

func findString(items []string, target string) (int, bool) {
	// items 必须已经按升序排列，sort.Find 只负责在这个范围内二分查找。
	return sort.Find(len(items), func(i int) int {
		// target 放在左侧，比较结果会对应“前缀正、中间零、后缀负”。
		return strings.Compare(target, items[i])
	})
}

func main() {
	items := []string{"apple", "banana", "lemon", "mango", "pear"}
	// 未命中时，返回的下标就是保持升序的候选插入位置。
	index, found := findString(items, "orange")
	fmt.Println(index, found)
}

这个例子中，orange 应位于 mango 与 pear 之间，所以返回的候选位置是它们之间的下标。这里的重点不是手算某个输出，而是比较器必须始终对同一组有序数据保持一致方向。

读取 i 和 found

调用结果要同时看两个值。found 为真时，可以安全地把 items[i] 当作命中元素；为假时，i 仍然有价值，但它表示插入边界，而不是一个已经存在的元素。

func locate(items []string, target string) {
	// 比较器返回目标与当前元素的三态关系，避免把 bool 条件方向写反。
	i, found := sort.Find(len(items), func(i int) int {
		return strings.Compare(target, items[i])
	})

	if found {
		// 只有命中时才读取 items[i]，避免把 i==len(items) 当成有效下标。
		fmt.Printf("命中：%s，位置：%d\n", items[i], i)
		return
	}
	// 未命中时 i 是 lower-bound 位置；它可以等于 len(items)。
	fmt.Printf("未命中，插入位置：%d\n", i)
}

重复值也要提前定规则。sort.Find 返回的是满足条件的最小位置，因此有重复目标时会落到重复区间的左边界。若业务要插到重复区间右侧，需要在明确的比较规则下另行寻找右边界，不能把 found 当成“唯一值保证”。

把未命中位置用于有序插入

得到插入位置后，可以用一次扩容和移动把新元素放进切片。这个动作会改变底层切片，因此调用方应明确是否允许修改原切片；示例将结果作为新切片返回，避免把副作用藏在定位函数里。

func insertSorted(items []string, target string) []string {
	// 先用同一套比较规则找到 lower-bound，命中和未命中都能复用位置。
	i, _ := sort.Find(len(items), func(i int) int {
		return strings.Compare(target, items[i])
	})

	// 扩大一个元素后右移尾部，给插入值腾出位置。
	items = append(items, "")
	copy(items[i+1:], items[i:])
	items[i] = target
	return items
}

当 i==len(items) 时，copy 的源区间为空，追加动作自然变成尾部插入；当切片为空时，sort.Find(0, ...) 直接返回 0,false，同样可以走这条路径。

处理比较器方向和数据边界

sort.Find 依赖的是二分查找前提，不会替你检查切片是否真的有序。若比较器返回值在序列中来回变化，结果就没有可解释的插入意义。排查时可以按下面几项检查：

1. 确认切片与比较器使用同一种排序规则，例如都按字典序或都按忽略大小写后的值排序。
2. 确认 cmp(i) 比较的是目标与元素，而不是元素与目标；方向反了会让正负号分段关系反转。
3. 确认闭包捕获的目标值在查找期间不被修改，并且下标只用于访问 [0,n) 范围。
4. 确认 found=false 时不读取 items[i]，因为目标可能位于所有元素之后，i 可能等于长度。

如果只需要一个“第一个满足条件的位置”，sort.Search 仍然可以使用；但当你还要知道目标是否精确命中时，sort.Find 直接把这两个结果放在一起，代码边界会更清楚。

常见问题

sort.Find 会自动把切片排序吗？

不会。它要求调用方提供满足单调条件的比较器，输入数据的有序性由调用方保证。

found=false 时返回的 i 能直接访问吗？

不能直接假设可以访问。它可能等于切片长度；应把它当作插入边界，先判断是否命中。

重复值会返回哪一个下标？

函数返回满足 cmp(i) 的最小下标，因此通常是重复值区间的左边界。

sort.Find 和 sort.Search 怎么选？

只需要布尔条件对应的第一个位置时可用 sort.Search；需要同时区分精确命中和未命中插入位置时，sort.Find 更直接。