Go slices.BinarySearchFunc 查不到值是不是比较函数顺序写反了

我第一次把结构体切片交给 slices.BinarySearchFunc 时，看到明明存在的记录返回 found=false，很容易先怀疑二分查找“跳过了”目标。实际更常见的原因是比较函数方向写反，或者切片并没有按这一个比较规则保持有序。

官方地址：https://pkg.go.dev/slices#BinarySearchFunc

BinarySearchFunc 的比较函数签名是 func(E, T) int：返回负数表示切片元素排在目标前面，返回零表示匹配，返回正数表示切片元素排在目标后面。比较函数应当描述“元素相对目标”，不要把参数顺序倒成“目标相对元素”。

先把 cmp(E, T) 读成一条规则

这个函数接收切片中的一个元素和目标值。对升序切片来说，结果只有三种有用的含义：元素小于目标返回负数，元素等于目标返回零，元素大于目标返回正数。返回值的绝对数值没有特殊要求，符号和零才是二分边界需要的部分。

例如切片按 Score 升序排列，目标只是一个整数分数，可以这样写：

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type record struct {
	Name  string
	Score int
}

func main() {
	items := []record{
		{Name: "甲", Score: 10},
		{Name: "乙", Score: 20},
		{Name: "丙", Score: 35},
		{Name: "丁", Score: 50},
	}

	// 比较“切片元素”与“目标分数”，方向必须和升序切片一致。
	cmpScore := func(item record, target int) int {
		return cmp.Compare(item.Score, target)
	}

	// 返回的位置是 2，true 表示 Score=35 的元素命中。
	index, found := slices.BinarySearchFunc(items, 35, cmpScore)
	fmt.Println(index, found, items[index].Name)
}

这里的 item 对应类型参数 E，target 对应类型参数 T。当检查到分数 20 和目标 35 时，比较结果应为负数，二分查找才知道目标还在右侧。

切片必须按同一比较规则有序

“有序”不是只看数据表面上是否从小到大，而是要看 cmp 定义的字段和方向。上面的切片按 Score 升序排列，因此 cmp.Compare(item.Score, target) 才能把小分数稳定地归到目标左侧。

下面三种变化都会破坏这个前提：

可以先用同一个比较函数检查相邻元素的顺序。这个检查的目的不是替代搜索，而是把“数据没有按搜索规则有序”从“比较函数参数写反”中分离出来。

package main

import (
	"cmp"
	"fmt"
)

type record struct {
	Name  string
	Score int
}

func sortedByScore(items []record) bool {
	for i := 1; i  0 {
			return false
		}
	}
	return true
}

func main() {
	items := []record{{"甲", 10}, {"乙", 35}, {"丙", 20}}
	fmt.Println(sortedByScore(items)) // false：20 应排在 35 前面
}

比较函数写反后，二分边界为什么会错

标准库实现维护的是一个边界：左边的元素都满足 cmp(element, target) ，右边的元素都满足 cmp(element, target) >= 0。每次取中点，如果中点元素“排在目标前面”，就把左边界移到中点右侧；否则收紧右边界。

最容易写错的是把参数交给 cmp.Compare 时倒过来：

// 错误示例：返回的是“目标相对元素”的结果，方向与 BinarySearchFunc 契约相反。
wrong := func(item record, target int) int {
	return cmp.Compare(target, item.Score)
}

// 正确示例：返回“元素相对目标”的结果。
right := func(item record, target int) int {
	return cmp.Compare(item.Score, target)
}

以元素 20、目标 35 为例，正确写法得到负数，表示 20 在目标前面；写反后得到正数，二分会把它当成“元素已经在目标后面”。这不是简单的返回值风格差异，而是直接改变了搜索空间的收缩方向。

因此遇到“存在值却查不到”，可以先固定一个中间元素手算三件事：元素值、目标值，以及比较函数的符号。只要某个元素在实际排序位置上应该小于目标，却返回了正数，就应先修正比较函数或排序规则。

没找到时，返回的 index 仍然有用

BinarySearchFunc 返回的第一个值不是“只有命中才有意义”。当 found=false 时，它表示目标按当前排序规则应该插入的位置。

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type record struct {
	Name  string
	Score int
}

func main() {
	items := []record{{"甲", 10}, {"乙", 20}, {"丙", 35}, {"丁", 50}}

	// 30 应位于 20 和 35 之间，因此返回插入位置 2。
	index, found := slices.BinarySearchFunc(items, 30, func(item record, target int) int {
		return cmp.Compare(item.Score, target)
	})
	fmt.Println(index, found) // 2 false

	// 未命中时再插入，必须在同一个比较规则下维护有序性。
	if !found {
		items = slices.Insert(items, index, record{Name: "新记录", Score: 30})
	}
	fmt.Println(items[index].Score) // 30
}

这也提供了一个很实用的排错信号：如果你预计目标 30 应该落在索引 2，却得到明显不合理的位置，优先检查切片是否真的按 Score 升序，以及比较函数是否把元素和目标写反。

重复值和结构化目标怎么处理

当多个元素在比较函数看来相等时，搜索结果应围绕同一个等价规则理解。二分边界会先找到不再小于目标的位置，因此重复值场景不要把返回的索引理解成“最后一个相等元素”。如果业务需要最后一个匹配项，应在命中后继续向后扫描，或设计单独的上界查找逻辑。

如果目标本身也是结构体，仍然只要保持参数方向一致即可：

// 结构体切片和结构体目标都按 Code 字段升序比较。
cmpCode := func(item record, target record) int {
	return cmp.Compare(item.Name, target.Name)
}

// 这里的 target 只是搜索键；不要在函数内部临时改用另一个排序字段。
index, found := slices.BinarySearchFunc(itemsByName, record{Name: "丙"}, cmpCode)
_ = index
_ = found

排查顺序可以固定成四步

1. 先看签名：确认比较函数是 func(E, T) int，第一个参数是切片元素。
2. 再看符号：元素小于目标必须返回负数，匹配返回零，大于目标返回正数。
3. 然后看有序性：切片必须按同一字段、同一升降序和同一等价规则排列。
4. 最后看返回值：结合 index 和 found 判断是目标不存在，还是边界已经不可信。

所以，BinarySearchFunc 查不到值时，比较函数顺序写反确实是第一批应检查的问题，但不是唯一原因。只要牢牢记住“元素相对目标”的方向，并让切片与比较函数共享同一排序契约，返回的索引就能同时承担命中位置和插入位置两种职责。

为什么不能直接返回 bool？

因为调用方经常还需要知道目标应该位于哪里。索引让未命中场景可以直接定位插入点，也方便发现排序前提是否被破坏。

比较函数返回 -1 和 1 才安全吗？

不需要。标准库只依赖负数、零、正数的符号，使用 cmp.Compare 可以避免手写分支时漏掉相等情况。

切片是降序时还能用吗？

可以，但必须让切片和比较函数共同表达降序关系。不要只把比较函数改成降序，却保留按升序排列的数据。

目标不存在时应该怎么插入？

当 found=false 时，返回的 index 就是按当前比较规则的插入位置；插入后仍要保持同一比较契约。