Go sort.Search 找不到元素时为什么返回 len：边界闭区间与插入位置

在一个已经升序排列的分数表里查找“第一个不低于 80 分”的位置，很多人第一次使用 sort.Search 时会困惑：目标不存在，函数为什么不返回 -1，而是返回切片长度 len？答案是它查找的不是“相等元素”，而是单调条件第一次成立的位置；如果所有位置都不满足，插入点自然就在末尾。

sort.Search(n, f) 返回 [0,n) 中第一个让 f(i) 为 true 的下标；如果没有任何下标满足条件，就返回 n。这个 n 表示“应插入末尾”，不是一次越界访问。

先看返回值：len 是末尾插入点

假设数据是 []int{10, 20, 30, 40}，谓词写成 data[i] >= 35。前 3 个位置都为 false，第 4 个位置为 true，所以返回 3。若谓词改成 data[i] >= 50，4 个位置全部为 false，返回值就是 4，也就是 len(data)。

把“找相等”改写成“找第一个满足条件”

sort.Search 并不知道你的数组是什么，也不负责比较目标值。它只会反复调用谓词 f(i)，要求结果满足单调性：一段连续的 false 之后，剩下位置全部是 true。升序数组里常见的条件是 data[i] >= target，降序数组则需要重新设计谓词，不能直接照抄。

package main

import (
    "fmt"
    "sort"
)

func lowerBound(data []int, target int) int {
    return sort.Search(len(data), func(i int) bool {
        return data[i] >= target
    })
}

func main() {
    data := []int{10, 20, 30, 40}
    i := lowerBound(data, 35)
    fmt.Println(i, data[i]) // 3 40
}

这里的 i 是 lower bound：第一个不小于目标的位置。它不保证 data[i] 等于目标，所以这个示例如果查找 35，得到的是 40；要判断精确命中，必须先判断下标仍在数据范围内，再比较元素。

命中判断必须晚一步做

最容易出错的代码是直接写 data[i] == target。当 target 大于所有元素时，i == len(data)，此时访问 data[i] 会触发运行时越界。安全写法是先判断 i ：

func find(data []int, target int) (int, bool) {
    i := sort.Search(len(data), func(i int) bool {
        return data[i] >= target
    })
    if i == len(data) || data[i] != target {
        return 0, false
    }
    return i, true
}

空切片也遵循同一规则：传入的 n 是 0，返回值也是 0。它没有制造一个“特殊失败值”，调用方只需要把返回值当作边界位置处理。

插入新值时，不要把 len 当成异常

如果目标值不存在，返回位置正好可以用于保持切片有序。位置为 0 代表插到开头，位置在中间代表插入两个元素之间，位置等于 len 代表追加到末尾。真正的工程边界是：插入前确认数据有足够容量，或者使用新的切片接收结果。

func insertSorted(data []int, value int) []int {
    i := sort.Search(len(data), func(i int) bool {
        return data[i] >= value
    })
    data = append(data, 0)
    copy(data[i+1:], data[i:])
    data[i] = value
    return data
}

这个写法把重复值放在已有相等值之前，因为条件使用了 >=。如果希望插到相等值之后，可以改用 >，但谓词仍然要保持单调。

用边界用例验证谓词是否真的单调

排查二分查找问题时，先不要盯着返回值猜算法。把空数据、开头命中、中间插入、末尾未命中、重复值分别跑一遍。如果谓词结果出现 true 后又回到 false，sort.Search 的结果就没有可解释性。

func TestLowerBound(t *testing.T) {
    cases := []struct {
        name   string
        data   []int
        target int
        want   int
    }{
        {"empty", nil, 10, 0},
        {"front", []int{10, 20}, 5, 0},
        {"middle", []int{10, 20, 30}, 25, 2},
        {"end", []int{10, 20, 30}, 40, 3},
        {"duplicate", []int{10, 20, 20, 30}, 20, 1},
    }

    for _, tc := range cases {
        if got := lowerBound(tc.data, tc.target); got != tc.want {
            t.Fatalf("%s: got %d, want %d", tc.name, got, tc.want)
        }
    }
}

相关问答

sort.Search 找不到值时能否当成 -1？

不能。它返回的是插入位置，所有元素都不满足时就是 len。需要 -1 的接口应由业务层在边界检查后自行转换。

为什么不能把谓词写成 data[i] == target？

相等关系通常不是单调的，结果可能是 false、true、false，无法满足二分搜索要求。应使用 >= 或 > 找边界，再做精确比较。

返回 len 后直接 append 是否安全？

作为插入位置可以安全使用；但移动元素前仍要确认切片可扩展，并用 append 增长长度后再 copy。

记住“边界位置”这个抽象

sort.Search 的返回值不是“有没有找到”的单一答案，而是一个边界位置。先用单调谓词找到第一个满足条件的下标，再根据 i == len(data) 判断是否落在末尾，最后决定是精确命中、插入还是返回未找到。把这三步拆开，len 就不再是令人意外的结果。