Go sort.Find 的有序切片定位方法

在升序切片中查找一个目标值时，sort.Find 可以直接返回“最小匹配下标”和“是否命中”两个结果。关键不是把比较函数写成布尔值，而是让 cmp(i) 按“目标值与当前元素的比较结果”返回正数、零或负数：目标值更大返回正数，相等返回零，更小返回负数。这样即使目标不存在，返回的 i 也可以作为保持有序的插入位置。

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

sort.Find(n, cmp) 返回范围 [0,n) 中第一个满足 cmp(i) 的下标；只有下标仍在切片范围内且比较结果等于零时，found 才是 true。

先看懂 sort.Find 的返回值

函数签名是 Find(n int, cmp func(int) int) (i int, found bool)。n 通常传入切片长度，回调只接收下标；它不直接接收目标值，需要通过闭包捕获目标值和切片。

• cmp(i) > 0：目标值大于当前位置的元素，搜索应继续向右。
• cmp(i) == 0：当前位置与目标值相等，可能是答案。
• cmp(i) ：目标值小于当前位置的元素，搜索应收缩到左侧。
• found == false 时，i 不是错误标记，而是目标值应插入的位置。

用 cmp 把目标值映射成正零负

下面的示例使用升序整数切片。比较时采用“目标值减当前元素”的方向，目标值在右侧时返回正数，在左侧时返回负数，正好满足 sort.Find 对三段单调区域的要求。

package main

import (
    "fmt"
    "sort"
)

func main() {
    values := []int{3, 8, 13, 21, 34, 55}
    target := 21

    index, found := sort.Find(len(values), func(i int) int {
        // 返回“目标值 - 当前值”，让回调结果保持正、零、负三段。
        return target - values[i]
    })

    if found {
        // found 为 true 时，index 就是相等元素的下标。
        fmt.Printf("找到 %d，索引为 %d\n", target, index)
        return
    }

    // 未命中时 index 是保持升序所需的插入位置。
    fmt.Printf("未找到 %d，应插入索引 %d\n", target, index)
}

这里的比较方向也可以写成 compare(values[i], target)，但必须同步调整正负含义。不要只看到“返回一个整数”就随意写成 values[i] - target；方向反了，回调可能不再满足二分查找需要的分段顺序。

found 为 false 时如何使用 i

例如目标值为 20，它位于 13 与 21 之间。sort.Find 会返回下标 3，因为在该位置插入 20 后，切片仍然是升序；此时 found 为 false。

func locate(values []int, target int) (int, bool) {
    // 空切片也能工作：len(values) 为 0 时直接返回 (0, false)。
    index, found := sort.Find(len(values), func(i int) int {
        // 闭包只读取二分查找访问到的合法下标。
        return target - values[i]
    })
    return index, found
}

func main() {
    values := []int{3, 8, 13, 21, 34, 55}
    index, found := locate(values, 20)

    // found 为 false 时，不要把 index 当成 -1 或有效命中下标。
    fmt.Println(index, found) // 3 false
}

与 strings.Index 等 API 不同，sort.Find 不使用 -1 表示未找到。如果目标大于所有元素，返回值会是 len(values)；因此使用下标访问元素前，仍需先判断 found 或检查 index 。

重复值、空切片和边界值

当切片中存在多个相等值时，sort.Find 返回最小的相等下标。例如 []int{2, 7, 7, 7, 11} 查找 7 时，返回下标 1，而不是中间或最后一个 7。这适合把重复区间的起点作为后续范围处理的入口。

这些结果都依赖输入数据已经按照同一个比较方向排序。若切片无序，或比较函数对相邻位置的结果在正、零、负之间来回跳变，二分查找没有可依赖的单调结构，返回值就不能按上述语义解释。

使用 sort.Find 前的核对清单

1. 确认传入的 n 与可索引数据长度一致。
2. 确认切片按比较函数对应的顺序排列，升序和降序不要混用。
3. 确认 cmp(i) 对目标值依次呈现正数、零、负数三段，任意一段都可以为空。
4. 先读取 found，再把 i 当作命中下标使用。
5. 把未命中的 i 当作插入位置，而不是当成错误值。

常见问题

sort.Find 和 sort.Search 怎么选？

sort.Find 直接表达三态比较并返回 found；如果只需要寻找第一个满足布尔条件的位置，可以使用 sort.Search，但命中判断通常要由调用方再比较一次。

cmp 能否返回任意正数或负数？

可以，函数只关心正、零、负三种符号，不要求返回值一定是 1、0、-1。使用差值时要留意整数溢出风险；对极大整数或自定义类型，按分支返回固定符号通常更稳妥。

为什么目标不存在时不能判断 i == -1？

因为 sort.Find 的未命中结果是插入位置：可能是中间位置，也可能等于切片长度。是否命中应使用第二个返回值 found。