Go slices.BinarySearch 怎样复用已有缓冲空间

如果一批整数已经放在调用方的切片里，想连续查询多个目标值，slices.BinarySearch 不需要创建新的结果切片。它直接读取这块递增有序的已有缓冲区，返回一个索引和一个布尔值：命中时索引指向元素，未命中时索引表示目标值应插入的位置。

官方文档：https://pkg.go.dev/slices#BinarySearch

因此“复用已有缓冲空间”的关键不在于让 BinarySearch 修改切片，而在于让调用方长期持有一份有序 slice，把它作为只读查询缓冲区反复传入。查询本身只产生两个标量返回值，不会替每个目标值分配一个新数组。

一、先确认 BinarySearch 能复用什么

函数签名是：

func BinarySearch[S ~[]E, E cmp.Ordered](x S, target E) (int, bool)

其中 x 必须按递增顺序排列。返回的第一个值是目标值所在的位置；如果没有命中，它是目标值按排序规则应该出现的位置。第二个值才是“是否真的找到”。

这带来三个明确边界：

• 它读取切片元素，不负责替调用方排序。
• 它返回 int 和 bool，不是新的结果 slice。
• 如果底层数据后来被改乱，原来的有序前提就失效，复用前必须重新排序或拒绝查询。

二、让调用方准备一块有序缓冲区

先在数据进入查询阶段时完成一次排序。排序会调整已有数组中的元素，之后的多次搜索只读取这份结果。下面的示例把切片作为参数传入，函数内部不复制它：

package main

import (
	"fmt"
	"slices"
)

func main() {
	// 这块切片由调用方持有，后续查询都复用它的底层缓冲区。
	buffer := []int{42, 7, 19, 7, 31, 12}
	slices.Sort(buffer)

	// 排序结果是 [7 7 12 19 31 42]，满足 BinarySearch 的前提。
	for _, target := range []int{7, 20, 42} {
		index, found := slices.BinarySearch(buffer, target)
		fmt.Printf("target=%d index=%d found=%t\\n", target, index, found)
	}
}

这里的 buffer 只有一份。循环每次传入同一个 slice 头，返回的只是整数索引和布尔值。对于重复值，标准库返回相等元素中最早的位置，所以示例中的目标值 7 会落在两个连续的 7 的第一个位置。

三、封装一个复用缓冲区的查询函数

在实际项目中，可以把“缓冲区必须有序”的责任放在构造或加载阶段，再让查询函数只接受只读语义的 slice。Go 没有只读切片类型，因此约定函数不修改传入参数，并在命名和注释中写清楚：

package lookup

import "slices"

// SearchResult 表示一个目标值在共享有序缓冲区中的位置结论。
type SearchResult struct {
	Target int
	Index  int
	Found  bool
}

// SearchMany 复用 sorted 进行多次二分查询，不复制底层元素。
// 调用方必须保证 sorted 按递增顺序排列，函数也不会修改它。
func SearchMany(sorted []int, targets []int) []SearchResult {
	// 结果数量通常与目标数量一致；一次分配结果容器即可，避免每次查询单独扩容。
	results := make([]SearchResult, 0, len(targets))
	for _, target := range targets {
		index, found := slices.BinarySearch(sorted, target)
		results = append(results, SearchResult{
			Target: target,
			Index:  index,
			Found:  found,
		})
	}
	return results
}

这段代码没有复制 sorted，但它会为返回值集合分配一块 SearchResult 数组。如果调用方还希望完全复用结果缓冲区，可以继续把结果 slice 作为参数传入并用 results[:0] 清空长度；这属于结果容器复用，不要和 BinarySearch 是否分配混为一谈。

四、空切片、重复值和未命中位置怎么处理

BinarySearch 对空切片也能返回结果：索引为 0，命中值为 false。这个位置表示如果向空切片插入目标值，它应该位于开头。未命中时同样要先检查 found，不能只依据索引做读取：

package main

import (
	"fmt"
	"slices"
)

func describe(sorted []int, target int) string {
	index, found := slices.BinarySearch(sorted, target)
	if found {
		// 命中时 index 才能作为 sorted 的有效元素下标。
		return fmt.Sprintf("命中：sorted[%d]=%d", index, sorted[index])
	}

	// 未命中时 index 是插入点，可能等于 len(sorted)，不能直接下标读取。
	return fmt.Sprintf("未命中：插入位置为 %d", index)
}

func main() {
	// 空切片与重复值都属于合法输入，结果由 found 区分。
	fmt.Println(describe([]int{}, 10))
	fmt.Println(describe([]int{2, 2, 5, 9}, 2))
	fmt.Println(describe([]int{2, 2, 5, 9}, 8))
}

如果业务要把未命中的目标插入原切片，可以使用返回位置作为插入点，再调用 slices.Insert 或自行维护容量。但插入会改变切片内容；下一次查询前仍要保证它保持递增有序，不能把“查询缓冲区复用”理解成“数据可以随意修改”。

五、常见误区与分配检查

如果需要确认查询函数没有因为自己的逻辑复制输入，可以围绕调用方代码做基准测试，并观察分配次数；不要把构造测试数据、结果容器分配或日志格式化的开销算到 BinarySearch 本身。核心优化点是：有序数据只准备一次，多个目标值共享它，搜索结果只用两个标量表达。

总结

复用已有缓冲空间的正确做法是：调用方先把 slice 排成递增顺序，再把同一个 slice 反复传给 slices.BinarySearch。该函数不会创建新的结果数组，命中返回最早索引，未命中返回插入位置；业务代码只需要正确处理 found，并在任何数据变更后恢复有序前提。

相关问题

• BinarySearch 能搜索未排序的切片吗？不能，未排序输入会破坏插入点和命中判断的前提。
• 未命中的索引可以直接读取吗？不可以，它可能等于切片长度，必须先判断 found。
• 重复值返回哪个位置？返回相等元素中最早的位置。
• 查询结果本身完全不分配吗？BinarySearch 只返回两个标量；如果调用方收集多个结果，结果容器仍可能分配。