Go sort.Find 怎样定位有序切片中的匹配范围

当有序切片里出现重复值时，单纯拿一个“可能位置”不够：你还要知道它是否真的命中，以及没有命中时应该插在哪里。sort.Find 的直接用法是返回 i, found := sort.Find(len(data), cmp)，其中 i 是第一个满足 cmp(i) 的位置，found 只在该位置确实相等时为 true。

官方文档地址：https://pkg.go.dev/sort

这套 API 的关键不是“再写一个二分查找”，而是把比较函数写成稳定的三段：前面为正数，中间相等为零，后面为负数。数据本身不满足这个顺序，返回值就没有可解释性。

问题从“只拿一个位置”开始

一个标签索引按名称排序后，业务希望定位某个名称的连续记录。之前用 sort.Search 可以找到第一个大于等于目标的位置，但命中判断要另写；如果只把返回的索引当成“找到了”，未命中时就会误把插入点当成结果。

package main

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

func main() {
    // 数据必须按名称升序排列，重复名称允许连续出现。
    names := []string{"api", "cache", "cache", "worker"}
    target := "cache"

    // cmp 返回目标值与当前元素的三态比较结果。
    index, found := sort.Find(len(names), func(i int) int {
        return strings.Compare(target, names[i])
    })

    // found 表示真正相等；index 在未命中时仍是可用的插入点。
    fmt.Println(index, found)
}

按这组数据的排序关系，index 指向两个 cache 的第一个位置，found 为 true。如果目标改成 db，索引会落在 worker 之前，found 为 false；这个位置可用于插入，但不能当作已存在的元素。

比较函数为什么必须形成正、零、负三段

sort.Find 的比较函数不是任意返回整数的回调。官方源码要求：前缀的 cmp(i) 大于零，中间的匹配段等于零，后缀小于零；三段都可以为空。对升序字符串，strings.Compare(target, names[i]) 正好表达“目标值排在当前元素之后、相等、排在之前”。

常见根因是把比较方向写反。若改成 strings.Compare(names[i], target)，正负分段会反过来；除非同时按降序重新设计数据和契约，否则二分搜索假设被破坏。另一个根因是切片中途被追加了未排序数据：比较函数看起来没错，但整个范围已经不是单调分段。

found 和插入位置要一起看

返回的索引只有两个稳定解释：命中时，它是相等区间的起点；未命中时，它是目标值应插入的位置。如果所有元素都小于目标，索引可能等于 n，此时不能访问 data[index]。因此读取元素前必须先判断 found 或先判断索引小于长度。

func findName(names []string, target string) (string, bool, int) {
    // names 必须已按升序排列；index 可能等于 len(names)。
    index, found := sort.Find(len(names), func(i int) int {
        return strings.Compare(target, names[i])
    })
    if !found {
        return "", false, index // index 是插入点，不是有效元素值。
    }
    return names[index], true, index // 重复值从第一个相等位置开始。
}

如果要拿到全部相等元素，可以从这个起点向右扫描，直到值变化；如果只关心是否存在，found 已经足够。不要把 sort.Find 的返回结果说成“匹配范围的首尾”，它只返回首个相等位置和布尔值，范围终点需要业务代码另行计算。

排查返回结果不对时，先看四个边界

第一，确认 n 与比较函数访问的范围一致；把大于切片长度的数传进去会造成越界风险。第二，确认比较函数只读取 [0, n) 内的元素，不要把外部可变状态混入比较。第三，确认目标和数据使用同一排序规则，例如大小写折叠、自然排序或字节序不能在两处各写一套。第四，重复值只会让 found 指向第一个相等位置，不会自动返回最后一个或整个区间。

相关问题

sort.Find 会返回所有重复值吗？不会，它只返回第一个相等位置和 found；终点要自己向右扫描。

未命中时 index 是多少？是保持排序所需的插入位置，可能等于切片长度。

可以给未排序切片使用吗？不应这样做；先建立稳定排序，再调用 Find。

把 sort.Find 当成“带命中标记的下界查找”更准确：数据顺序、比较方向和边界先成立，返回的索引才有意义。