Go sort.Search实现有序切片插入位置查找

在升序切片里找一个值应该插在哪里，最稳妥的写法不是从头比较，而是让 sort.Search 找到第一个满足条件的下标。对目标值 x，把谓词写成 values[i] >= x，返回的就是 lower bound：它既可能指向相等元素，也可能等于切片长度，正好覆盖尾部插入。

把插入位置转成 sort.Search 能判断的条件

我在处理一组按数值排序的配置项时，真正需要的不是“有没有这个值”，而是“第一个不小于目标值的位置”。这类位置可以看成一条边界：边界左侧的元素都小于目标，边界及右侧的元素都大于等于目标。

sort.Search(n, f) 的关键约定是：在 0 到 n-1 上，f 必须先返回 false，之后连续返回 true。它通过二分查找定位第一个 true，而不是替你比较元素，所以单调性来自谓词本身。

用 sort.Search 找到升序切片的 lower bound

最小可用函数只需要切片长度和一个闭包。闭包捕获目标值，返回第一个大于等于它的位置：

package main

import (
    "fmt"
    "sort"
)

func lowerBound(values []int, target int) int {
    // 只有“先 false、后 true”的谓词才能满足二分查找前提。
    return sort.Search(len(values), func(i int) bool {
        // 第一个大于等于 target 的位置就是插入点。
        return values[i] >= target
    })
}

func main() {
    values := []int{10, 20, 20, 40}
    fmt.Println(lowerBound(values, 20)) // 1：指向第一个 20
    fmt.Println(lowerBound(values, 30)) // 3：位于 20 与 40 之间
    fmt.Println(lowerBound(values, 50)) // 4：等于 len(values)，追加到末尾
}

返回值为 len(values) 并不是失败，而是“所有元素都小于目标”。空切片也自然返回 0，因此不需要额外写一个空判断。

重复值、首尾位置和容量扩展要分开处理

查到位置只是第一半。如果确实要把目标插入切片，还要先扩展一个元素，再从插入点开始向后移动。下面的函数采用 lower bound 策略：相同值会插到已有相同值的最前面。

func insertSorted(values []int, target int) []int {
    // 找到相等值的最前位置，保证结果仍然按升序排列。
    index := sort.Search(len(values), func(i int) bool {
        return values[i] >= target
    })

    // append 先获得一个尾部空位；容量不足时会自动分配新数组。
    values = append(values, 0)
    // copy 从后向前的重叠移动，把 index 位置留给 target。
    copy(values[index+1:], values[index:len(values)-1])
    values[index] = target
    return values
}

// 如果重复值应排在已有值后面，把谓词改成 values[i] > target。

这个写法会修改原底层数组（若容量足够），调用方若仍持有同一切片的其他视图，需要提前约定这一点。若希望完全隔离，可以先复制一份再插入。

用表格和完整函数复查边界

最后再强调一个容易忽略的边界：sort.Search 不会检查切片是否有序。如果输入在某个位置先出现 true、后又出现 false，二分结果就没有可靠意义。生产代码中应把“保持升序”作为数据结构不变量；若无法保证，就先排序或改用线性扫描。

相关问题

sort.Search 会返回目标值的下标吗？

它返回的是边界下标，不承诺目标一定存在。需要确认相等时，应先判断返回位置是否小于切片长度，再比较 values[index] == target。

为什么不用 sort.SearchInts？

整数升序切片可以直接用 sort.SearchInts(values, target)。自定义结构体、复合键或特殊比较规则则使用通用的 sort.Search 更灵活。

怎么把插入策略改成排在重复值后面？

把谓词从 values[i] >= target 改为 values[i] > target，得到 upper bound，再按同样的移动逻辑插入即可。