Go sort.Search 如何控制边界条件

使用 sort.Search 时最容易混淆的一点是：它不是“找到就返回下标”，而是在 [0, n) 中寻找谓词第一次为 true 的位置。谓词必须满足“前面全是 false，后面全是 true”的单调边界；如果没有 true，返回值就是 n。因此，控制边界的核心不是多写一个循环，而是把比较条件和返回值判定分开。

先把 sort.Search 理解成一条单调边界

sort.Search(n, f) 只保证在 0 到 n-1 的范围内调用 f。对升序数据，假设目标是 23，比较式 data[i] >= 23 会形成一段 false 和一段 true：小于 23 的位置属于前缀，23 及之后的位置属于后缀。Search 返回后缀的第一个下标，也就是常说的 lower bound。

这个约束决定了闭包不能随意返回一个会来回变化的条件。若数据未排序，或者比较字段在切片中不是单调变化，二分查找即使返回了一个下标，也没有可解释的边界意义。

用 n 和短路判断处理空切片与末尾位置

最小可用写法如下。代码里的 i 是必要的，因为目标大于所有元素、切片为空时，返回值都会落在切片尾部。

package main

import (
	"fmt"
	"sort"
)

func find(data []int, x int) (int, bool) {
	// data 必须按升序排列；Search 返回第一个 data[i] >= x 的位置。
	i := sort.Search(len(data), func(i int) bool {
		return data[i] >= x
	})
	// 先判断 i 是否仍在切片内，再读取 data[i]，避免尾部越界。
	found := i 

这里的返回值有两层含义：found 表示是否存在精确值，i 则始终是候选边界。目标值为 10 时，i 会指向 15；目标值为 30 时，i == len(data)，它仍然可以作为“追加位置”或“没有更大等值候选”的信号。

按数据方向和重复值选择正确谓词

升序数据要找第一个大于等于目标值的位置，使用 >=；降序数据则把方向反过来，找第一个小于等于目标值的位置，使用 。不要只改排序函数而忘记闭包比较方向，否则边界会落在错误的一侧。

如果业务需要“最后一个小于等于 x”的位置，通常要换成另一个单调谓词，再对返回位置做一步调整；不要把一个不满足单调性的“前后都想判断”条件塞进 Search。二分查找能否成立，取决于边界是否唯一且方向一致。

把候选索引接入插入和验收逻辑

把 i 作为插入位置时，原切片应保持有序；把它作为命中结果时，则必须同时满足范围和相等两个条件。工程上可以固定检查下面四种输入：

• 空切片：返回 0，不能读取元素。
• 目标小于首元素：返回 0，表示插入到最前面。
• 目标位于中间：返回右侧第一个不小于它的位置。
• 目标大于末元素：返回 len(data)，表示追加位置。

func insertIndex(data []int, x int) int {
	// 该谓词与插入语义一致：i 左侧都小于 x，i 右侧从 x 开始。
	return sort.Search(len(data), func(i int) bool {
		return data[i] >= x
	})
}

// 调用方应在插入前保证 data 已按升序维护；Search 本身不会替你排序。

最后记住，sort.Search 的性能优势建立在“数据已经有序、谓词单调、访问边界安全”这三个前提上。前提不成立时，先修正数据模型或比较函数，再讨论二分查找本身。

常见问题

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

它返回 n，因为这个值天然表示插入到末尾的位置；调用方应通过 i 区分它和有效元素下标。

有重复值时如何拿到第一个匹配项？

对升序数据使用 data[i] >= x，再检查 data[i] == x。Search 返回的就是第一个满足下界条件的位置。

数据是降序还能使用 sort.Search 吗？

可以，但闭包要使用与降序一致的 data[i] ，并继续保证谓词呈现单调的 false 前缀和 true 后缀。