Go sort.Search 找不到目标时怎么检查谓词的单调性

sort.Search 找不到目标时，先别把锅甩给二分查找本身。它返回的是谓词第一次为 true 的位置，不是“目标值是否相等”的结果；只要谓词在范围内满足“前面全是 false，后面全是 true”，返回值就有明确含义。没有任何 true 时返回 len(data)，不是 -1。

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

排查口诀：先看布尔序列是否只有一个 false→true 边界，再看数据顺序和比较符是否配对；返回索引后，仍要单独判断 data[i] 是否等于目标。

先判断返回值：n 是未命中，不是 -1

我遇到这类问题时，第一步会把“查找位置”和“命中结果”拆开。升序切片中，data[i] >= target 表示“从这里开始达到下界”，所以 Search 找到的是第一个满足下界的位置。目标比所有元素都大时，所有谓词结果都是 false，返回值自然就是 len(data)。

package main

import (
	"fmt"
	"sort"
)

func main() {
	data := []int{10, 20, 30, 40}
	target := 35

	// >= 表达“从这个位置开始达到目标下界”，结果应先 false 后 true。
	i := sort.Search(len(data), func(i int) bool {
		return data[i] >= target
	})

	// Search 未命中时返回 len(data)，访问元素前必须先检查边界。
	found := i 

这个例子中 i 表示插入位置，found 才表示是否真的存在目标。把 i == -1 当成未命中会漏掉越过切片末尾的情况；反过来只判断 i ，又会把“第一个更大的元素”误报成命中。

检查谓词：必须先 false 后 true

sort.Search 不会替你验证闭包是否单调。比如把谓词写成 data[i] == target，在有重复值、目标缺失或中间位置出现相等时，布尔序列通常是 false、true、false，这已经不是它要求的边界形状。二分过程看到的只是局部判断，结果就不能再解释为“第一个相等位置”。

可以按下面三项复查：

1. 升序数据通常用 data[i] >= target，布尔结果应是若干个 false 后接若干个 true。
2. 降序数据把方向反过来，常用 data[i] ，仍然要形成同样的 false→true 边界。
3. 是否真正相等必须在返回后判断，不能把相等判断塞进一个不具备单调性的谓词里。

// 这个辅助函数只用于排查：把每个位置的谓词值打印成边界序列。
func printPredicate(data []int, target int) {
	for i, value := range data {
		// 升序下，达到下界后应保持为 true。
		fmt.Printf("i=%d value=%d predicate=%t\n", i, value, value >= target)
	}
}

如果输出出现 true 后又回到 false，先检查数据是否真的按当前方向排列，再检查闭包读取的字段是否和排序键一致。不要通过多调用几次 Search 来“碰”出正确结果，那只会掩盖谓词不满足契约的问题。

重复值、空切片和插入位置怎么处理

重复值是 Search 的优势场景：使用 >= 时，它会返回第一个大于等于目标的位置；再判断 data[i] == target，就能得到第一个命中位置。空切片时 n 为 0，返回值也是 0，不能直接读取 data[0]。

常见问题

sort.Search 找不到时为什么不是 -1？

它返回的是插入位置模型：如果所有元素都不满足谓词，插入位置就是 n。因此要先判断 i 。

能不能直接用 data[i] == target？

不建议。相等关系可能产生多个布尔段，不能稳定表达“首个 true”。应先用单调的下界或上界谓词找到边界，再单独判断相等。

谓词单调但数据一定有序吗？

不一定。Search 只依赖谓词结果满足 false→true 形态；常见做法是让谓词基于已经按对应方向排列的数据，但最终契约仍是闭包返回值的单调性。