Go sort.Find 如何处理有序切片：比较函数、插入点与不存在结果

线上服务把排序后的版本号列表交给查找函数时，最容易出现的误判不是“二分查找太复杂”，而是把 sort.Find 当成返回 -1 的普通查找。它真正返回的是第一个满足条件的位置，以及一个单独的命中标记；只要先把比较函数的方向写对，命中、插入和未命中三种结果就能统一处理。

sort.Find 返回第一个 cmp(i) 的索引；命中时 found=true，完全没有合适位置时返回 i=n，不是 -1。

缓存索引为什么会把未命中误判成异常

假设服务维护了一组已经按版本号升序排列的构建记录：["1.8", "1.10", "1.20", "1.21"]。查询 1.20 时，业务需要拿到记录；查询 1.19 时，业务又希望知道它应该插在 1.20 前面；查询比最后一项还大的 1.30 时，插入点则是切片长度。

如果把“不存在”写成 i == -1，1.30 会被当成合法索引之外的特殊值，后续代码很容易越界。sort.Find 把“位置”和“是否相等”拆开，正好适合这种索引场景。

先把 cmp(i) 写成目标值对第 i 项的比较

核心规则是：比较目标 target 与 versions[i]，目标小于当前项时返回负数，相等返回零，目标大于当前项时返回正数。下面这个闭包直接使用 strings.Compare，避免手写多个分支时把方向颠倒。

package main

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

func findVersion(versions []string, target string) (int, bool) {
	i, found := sort.Find(len(versions), func(i int) int {
		return strings.Compare(target, versions[i])
	})
	return i, found
}

func main() {
	versions := []string{"1.8", "1.10", "1.20", "1.21"}
	for _, target := range []string{"1.20", "1.19", "1.30"} {
		i, found := findVersion(versions, target)
		fmt.Printf("target=%s index=%d found=%t\n", target, i, found)
	}
}

运行后可以观察到三个结果：1.20 得到索引 2 且命中；1.19 得到索引 2 但未命中，这个位置就是插入点；1.30 得到索引 4，也就是 len(versions)。

二分查找真正依赖的是三段单调关系

sort.Find 并不是任意比较函数都能用。对有序数据，cmp(i) > 0 必须出现在前缀，cmp(i) == 0 可以出现在中间，cmp(i) 必须出现在后缀。比较目标为 1.19 时，实际序列的符号就是正、正、负、负。

这个约束解释了一个常见 bug：如果切片按降序排列却仍按升序写 strings.Compare(target, versions[i])，符号变化不再是单调的，函数可能返回一个看似合理但不可依赖的位置。此时应先统一数据顺序，或者改用与降序一致的比较定义。

用返回索引同时处理命中和插入

调用方应该把 found 当成第一判断条件。命中时可以读取 versions[i]；未命中时，i 仍然是有序插入点，但只有当 i 时才存在“插入点右侧的当前元素”。

func locate(versions []string, target string) string {
	i, found := findVersion(versions, target)
	if found {
		return fmt.Sprintf("命中 %s，索引 %d", versions[i], i)
	}
	if i == len(versions) {
		return fmt.Sprintf("未命中，追加到索引 %d", i)
	}
	return fmt.Sprintf("未命中，插入到 %s 前面，索引 %d", versions[i], i)
}

这段判断把尾部追加、区间插入和精确命中分开了。尤其要注意，空切片也会返回 i=0、found=false；不能看到索引为零就直接读取元素。

把三个边界案例放进测试

最小回归集至少包含命中、中间插入和尾部追加。再补一个空切片，能覆盖读取前的长度判断。

func TestFindVersion(t *testing.T) {
	versions := []string{"1.8", "1.10", "1.20", "1.21"}
	cases := []struct {
		target string
		wantI int
		wantFound bool
	}{
		{"1.20", 2, true},
		{"1.19", 2, false},
		{"1.30", 4, false},
	}
	for _, tc := range cases {
		i, found := findVersion(versions, tc.target)
		if i != tc.wantI || found != tc.wantFound {
			t.Fatalf("target=%s got (%d, %t)", tc.target, i, found)
		}
	}
}

测试重点不是验证二分查找的每一次中点，而是锁定对调用方有意义的契约：位置、命中标记，以及尾部返回长度。这样以后替换底层数据结构时，错误会在接口边界暴露。

几个容易混淆的边界

不要把 found=false 等同于索引无效

未命中只表示没有相等元素，不表示位置没有用途。中间未命中的索引是可用插入点，尾部未命中则等于长度。

不要把 sort.Find 和 sort.Search 的回调混写

sort.Search 接收布尔函数，寻找第一个为真的位置；sort.Find 接收返回负数、零或正数的比较函数，并额外给出 found。两者都要求单调性，但回调契约不同。

不要在比较函数里修改切片

二分查找会多次调用回调，回调应该是只读、稳定的比较过程。若调用期间改变 versions 的顺序，单调关系会失效，得到的结果也就没有可验证意义。

把 sort.Find 当成“位置加状态”的接口

在有序、可按索引访问的数据上，sort.Find 最有价值的地方不是少写几行二分代码，而是把精确命中和有序插入统一成一个返回值。实现时只记住三件事：比较目标与当前项、保证比较结果单调、先判断 found 再访问索引。

相关问题

sort.Find 未命中返回什么？返回第一个 cmp(i) 的位置；不存在这样的位置时返回 n，并且 found=false。

怎样判断返回位置能不能读取？只有 found=true 或明确满足 i 时才读取切片元素；尾部插入和空切片都不能直接读取。