Go slices 怎样用 BinarySearch 查找有序切片

如果一段 Go 数据已经按升序排好，想知道某个值是否存在，或者想知道新值应该插在哪里，直接使用 slices.BinarySearch。它返回两个结果：第一个是索引，第二个是 found。命中时索引指向目标值；未命中时索引仍然有用，它就是目标值保持有序时应插入的位置。

BinarySearch 先解决的是什么问题

slices 是 Go 标准库中的切片工具包。BinarySearch 的签名可以概括为：给定一个升序切片和一个目标值，返回目标值最早出现的位置，以及是否真的找到。整数、浮点数和字符串等满足有序比较约束的元素可以直接使用它。

这里的关键不是“它会自动排序”，而是“它在已经排序的数据上查找”。如果数据来自追加写入，调用前应先完成排序；查找过程中不要把切片内容改成破坏升序的状态。

package main

import (
	"fmt"
	"slices"
)

func main() {
	// 切片必须按升序排列，BinarySearch 才能返回可靠结果。
	prices := []int{10, 20, 35, 50, 80}

	// 命中时 index 指向目标值，found 表示确实存在。
	index, found := slices.BinarySearch(prices, 35)
	fmt.Println(index, found) // 2 true

	// 未命中时 index 是保持升序所需的插入位置。
	index, found = slices.BinarySearch(prices, 40)
	fmt.Println(index, found) // 3 false
}

这个例子中，40 应放在 35 和 50 之间，所以返回索引 3。它不代表“离目标最近的元素”，也不是最后一次比较的位置，而是可以直接用于插入的边界。

怎样读懂 index 和 found

实际代码中应始终同时处理两个返回值。命中时使用 found 保护索引访问；未命中时可以把 index 交给插入逻辑、范围判断或去重逻辑。

空切片也遵循同一规则：返回索引为 0、found=false。因此不要把 index=0 单独当成命中标志。

重复值为什么返回最早位置

有重复值时，BinarySearch 返回目标值第一次出现的位置。这一点适合做“是否存在”判断，也适合把一组相同值的范围从左边界开始定位。如果业务只需要任意一个匹配项，就不要依赖重复值中间某个位置的偶然结果。

package main

import (
	"fmt"
	"slices"
)

func main() {
	// 重复值仍需保持整体升序，返回值会指向最早的 7。
	levels := []int{3, 7, 7, 7, 12}
	index, found := slices.BinarySearch(levels, 7)

	// found 用来确认命中，index 用来读取第一处匹配。
	if found {
		fmt.Println("first match:", index, levels[index])
	}
}

结构体字段查找用 BinarySearchFunc

当切片元素是结构体，不能直接用普通 BinarySearch 比较整个结构体。这时使用 BinarySearchFunc，让比较函数只关注排序字段。比较函数返回负数、零或正数，分别表示切片元素排在目标前面、相等或排在目标后面。

package main

import (
	"fmt"
	"slices"
	"strings"
)

type User struct {
	Name string
	Age  int
}

func main() {
	users := []User{
		{Name: "Alice", Age: 30},
		{Name: "Bob", Age: 24},
		{Name: "Vera", Age: 41},
	}

	// users 按 Name 升序排列，比较函数也必须按 Name 判断先后。
	index, found := slices.BinarySearchFunc(users, User{Name: "Bob"}, func(item, target User) int {
		return strings.Compare(item.Name, target.Name)
	})
	if found {
		// 命中后再读取完整结构体，比较时忽略的 Age 不会丢失。
		fmt.Println(index, users[index].Name, users[index].Age)
	}
}

如果切片实际按年龄排序，比较函数却按姓名比较，结果就没有意义。排序字段、比较函数和后续插入逻辑必须使用同一套顺序；降序数据也不能直接套用普通升序规则。

把返回位置接到去重和有序插入

返回位置最实用的场景是“先查后写”。命中时不重复插入；未命中时，把新值插入到该索引处。下面的示例用 slices.Insert 复用同一个边界，避免重新手写移动元素的细节。

package main

import (
	"fmt"
	"slices"
)

func insertUnique(values []int, value int) []int {
	// 先取得命中状态和有序插入点，不命中时 index 仍可直接使用。
	index, found := slices.BinarySearch(values, value)
	if found {
		// 已存在就保持原切片内容，避免产生重复记录。
		return values
	}

	// 插入点来自二分查找，因此结果继续保持升序。
	return slices.Insert(values, index, value)
}

func main() {
	values := []int{10, 20, 50}
	values = insertUnique(values, 35)
	values = insertUnique(values, 20)
	fmt.Println(values) // [10 20 35 50]
}

需要注意，查找本身是对数级定位，但切片中间插入仍可能移动后续元素。数据量很大、插入频率很高时，应把“查找成本”和“搬移成本”分开评估，不能只因为用了二分查找就认为整个写入过程都是 O(log n)。

几个容易踩到的边界

• 无序切片：不要把无序数据直接传给 BinarySearch，先明确排序规则并完成排序。
• 降序切片：普通函数要求升序；如果使用自定义函数，比较规则必须和切片实际顺序完全一致。
• found 判断：索引为零不代表命中，必须检查第二个返回值。
• 重复值：命中后得到的是最早匹配位置，不要据此推断所有重复值的范围已经被返回。
• 自定义比较：比较函数返回零的条件要和业务的“相等”定义一致，否则可能把不同记录当成重复。

常见问题

BinarySearch 找不到时会返回 -1 吗？

不会。未命中时返回保持升序所需的插入位置，范围是 0 到 len(x)，再通过 found=false 表示目标不存在。

为什么不能把 map 或无序切片直接拿来二分查找？

二分查找依赖元素顺序来缩小范围。无序数据不满足这个前提，返回的索引就没有可靠含义；map 也没有可供该 API 使用的连续索引顺序。

官方 API 说明在哪里？

可以直接查看标准库文档：https://pkg.go.dev/slices#BinarySearch，自定义比较函数参见 https://pkg.go.dev/slices#BinarySearchFunc。如果需要确认该包的引入背景，也可阅读 https://go.dev/doc/go1.21。

总结一下：先保证切片顺序，再同时读取 index 和 found。命中时索引用于读取，未命中时索引用于插入；元素是结构体时，把排序字段准确写进 BinarySearchFunc 的比较函数。