Go slices.BinarySearchFunc 怎样在自定义顺序中查找

在自定义顺序中使用 slices.BinarySearchFunc，关键是让切片现有顺序与查询比较器保持一致。比较器的负数表示元素排在目标之前，零表示匹配，正数表示排在目标之后。分数降序也可以查，只需按降序解释先后关系，而不能沿用普通升序的比较器。

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

把漏查现象缩小到排序规则

设想一个榜单：原来按分数升序排列，后来展示需求改成降序，但查询代码仍按升序比较。这时“列表里明明有这个分数却找不到”并不能证明二分搜索有问题，首先应该对照两处比较规则。这里是用于解释问题的假设案例，不是线上事故记录。

这个问题通常在排序方向调整之后出现：展示顺序改变，搜索条件没有同步。二分搜索依赖有序分区，不会替调用方重新排序，也不会自动识别降序。只检查元素是否存在，而不检查其排序规则，会漏掉真正的触发条件。

统一排序与查询的比较语义

把分数比较封装成 scoreOrder。它对两个分数定义同一个顺序，再分别供排序比较器和查询比较器调用。对于降序，较高分数在目标之前，因此应返回负数。比如目标是84，95在它之前，72在它之后。

用结构体切片查找整数键

下面的独立示例使用Entry保存名称和分数，查询目标直接传整数。查询比较器接收一个Entry和一个整数，说明元素类型与目标类型可以不同，不需要为了查分数而临时构造完整对象。

package main

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

type Entry struct {
    Name string
    Score int
}

// 按分数降序定义先后，避免用减法比较引入溢出。
func scoreOrder(a, b int) int {
    return cmp.Compare(b, a)
}

func main() {
    rows := []Entry{{"青禾", 72}, {"远山", 95}, {"白露", 84}, {"溪石", 84}}
    // 排序和搜索都依赖 scoreOrder，不能一边降序一边升序。
    slices.SortFunc(rows, func(a, b Entry) int {
        return scoreOrder(a.Score, b.Score)
    })
    byScore := func(e Entry, target int) int {
        return scoreOrder(e.Score, target)
    }
    for _, target := range []int{84, 90, 60} {
        i, found := slices.BinarySearchFunc(rows, target, byScore)
        // 只有 found 为真才能把 i 当成命中元素下标。
        if found {
            fmt.Printf("分数=%d 下标=%d 命中分数=%d\n", target, i, rows[i].Score)
        } else {
            fmt.Printf("分数=%d 插入位置=%d\n", target, i)
        }
    }
}

按代码语义推导，分数排序为95、84、84、72；搜索84得到下标1且匹配为真，搜索90得到插入位置1，搜索60得到插入位置4。以上是示例的预期行为，未将它描述为本机执行日志。SortFunc不保证相等元素的原有相对次序，因此不能据此指定两个84分对象中的某个名称必然先出现。

解释首个匹配和插入位置

返回值由位置i与布尔值found组成。存在多个比较结果为零的元素时，返回最早匹配的位置；这个“匹配”由比较器决定，在示例里只表示分数相等，不表示名称也相同。未命中时，i表示保持当前顺序的插入位置，可能等于切片长度，不能直接访问rows[i]。

如果需要按“分数降序、名称升序”精确定位一个对象，排序器和查找器都应实现这一组合顺序，并让目标包含两个字段。若只是按分数定位同分组的起点，按分数降序且同分连续即可；定位后要取得整个同分组，可以从起点向后读取，直到分数不同或到达末尾。

空切片与nil切片都没有命中元素，返回位置0与false。查找本身不插入元素；若以后用这个位置插入新记录，还要遵守完整排序规则，尤其要考虑同分时名称等次级字段。

避免后续修改破坏顺序

修复比较器之后，还要把排序前提留在维护代码旁边。更改某条记录的Score、直接追加新记录或切换排序键，都可能破坏有序条件。更新之后应按相同顺序维护位置，或在重新排序之后再查。比较器应保持稳定，不能依赖会在查找期间改变的外部状态。

排查时可用IsSortedFunc配合同一个排序比较器帮助观察顺序，但不需要每次查询都做一次全表扫描。二分查找的比较次数随长度按对数增长；若每次查询前都重新排序，整体成本就包括排序，不能把整个业务操作都称为一次对数查找。

为什么比较器不直接返回分数相减？

大整数相减可能溢出，破坏符号判断。示例使用cmp.Compare并交换参数表达降序，使先后规则更清楚。

返回false是不是说明位置没有意义？

不是。位置仍表示目标在自定义顺序中的插入点，只是不能把它解释成已存在记录的下标。

能按名称搜索只按分数排序的切片吗？

通常不能。名称匹配需要满足名称比较器要求的顺序；换查询字段不会自动建立新的有序关系。

维护这段代码时，优先确认排序键、方向与比较器符号是否一致，再分别处理命中与插入位置。这比只围绕某个漏查目标修改条件更能避免同类问题反复出现。

参考：https://pkg.go.dev/slices#BinarySearchFunc