Go Academy · 课时

搜索已排序数据

Q: 「搜索已排序数据」课时是免费的吗？

是的 — 「搜索已排序数据」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Go Academy 课程的其余内容，请升级到 CoddyKit PRO。 Go Academy 课程共包含 4 节课。

Q: 「搜索已排序数据」这节课中我会学到什么？

二分搜索 你通过在浏览器中直接运行的动手代码来练习 Go Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

Q: 学习 Go Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Go Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。

Q: 「搜索已排序数据」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

Q: 我能在这节 Go Academy 课中编写并运行代码吗？

能。每节 Go Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

二分搜索

搜索已排序数据 是 CoddyKit 上的免费 Go Academy 课时。这是第 3 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Go Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Go Academy 课程共包含 4 节课。

为何搜索已排序的数据

切片排序后，您可以使用二分查找更快地查找元素，而不必扫描每一项。

Go 的 sort 包提供了以对数时间运行的搜索辅助函数。

线性查找与二分查找

线性查找会逐个检查元素（O(n)）。二分查找会在每一步将搜索范围缩小一半（O(log n)），但要求数据必须先排序。

sort.SearchInts

sort.SearchInts 会查找某个值所在的索引，或者查找将该值插入后仍能保持切片有序的位置。切片必须已经按升序排列。

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{1, 3, 5, 7, 9}
	i := sort.SearchInts(nums, 5)
	fmt.Println("index:", i)
}

确认匹配结果

SearchInts 即使在值不存在时也会返回一个索引（插入位置）。请始终通过检查 i < len(s) && s[i] == target 来确认匹配结果。

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{1, 3, 5, 7}
	target := 4
	i := sort.SearchInts(nums, target)
	found := i < len(nums) && nums[i] == target
	fmt.Println("index:", i, "found:", found)
}

插入位置

当某个值不存在时，返回的索引正是为了保持顺序而应插入该值的位置。这里，4 应插入索引 2 的位置。

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{1, 3, 5, 7}
	i := sort.SearchInts(nums, 4)
	fmt.Println("insert 4 at index:", i)
}

SearchStrings

sort.SearchStrings 对已排序的字符串切片执行相同的操作。

package main

import (
	"fmt"
	"sort"
)

func main() {
	words := []string{"apple", "cherry", "mango"}
	i := sort.SearchStrings(words, "cherry")
	fmt.Println("index:", i)
}

通用的 sort.Search

sort.Search 是灵活的核心函数。您需要向它提供一个长度和一个函数 f；该函数的返回值会先为 false，之后变为 true。函数会返回 f 为 true 的最小索引。

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{2, 4, 6, 8, 10}
	i := sort.Search(len(nums), func(i int) bool {
		return nums[i] >= 6
	})
	fmt.Println("first >= 6 at index:", i)
}

查找第一个大于阈值的元素

由于 sort.Search 会查找条件变为 true 的边界，因此它非常适合查找第一个大于某个阈值的值等问题。

package main

import (
	"fmt"
	"sort"
)

func main() {
	scores := []int{10, 20, 30, 40}
	i := sort.Search(len(scores), func(i int) bool {
		return scores[i] > 25
	})
	fmt.Println("first > 25:", scores[i])
}

必须先排序

二分查找以数据有序为前提。如果切片未排序，结果就没有意义。请始终先排序，再进行搜索。

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{9, 1, 5, 3}
	sort.Ints(nums)
	i := sort.SearchInts(nums, 5)
	fmt.Println(nums, "-> index of 5:", i)
}

性能提升

对于包含一百万个元素的切片，线性查找可能需要检查一百万项，而二分查找大约只需检查 20 项。一次排序的成本可以通过多次搜索得到回报。

选择搜索辅助函数

总结：

sort.SearchInts / SearchStrings / SearchFloat64s - 适用于类型明确的切片
sort.Search - 适用于可按索引访问的任意数据，并支持自定义条件

快速检查

您对一个不包含 4 的已排序切片调用 sort.SearchInts(s, 4)。它会返回什么？

回顾

使用二分查找搜索已排序的数据：

数据必须先排序
辅助函数会返回索引或插入位置
请使用相等性检查确认匹配结果
sort.Search 可以处理自定义条件

常见问题解答