Golang slices.BinarySearchFunc
最后修改于 2025 年 4 月 20 日
本教程将介绍如何在 Go 语言中使用 slices.BinarySearchFunc 函数。我们将涵盖使用自定义比较函数进行二分查找操作。
slices.BinarySearchFunc 函数在已排序的 slice 上执行二分查找。它使用自定义比较函数来确定元素的排序。
此函数对于在大型已排序集合中进行搜索非常高效。它会返回目标值在保持顺序的情况下应该插入的位置。
基本的 BinarySearchFunc 示例
最简单的用法是在已排序的 slice 中搜索数字。我们定义一个返回 -1、0 或 1 的比较函数。
package main
import (
"fmt"
"slices"
)
func main() {
numbers := []int{1, 3, 5, 7, 9}
cmp := func(a, b int) int {
if a == b {
return 0
} else if a < b {
return -1
}
return 1
}
pos, found := slices.BinarySearchFunc(numbers, 5, cmp)
fmt.Printf("Position: %d, Found: %v\n", pos, found)
}
比较函数遵循标准的排序规则。搜索在 slice 的第 2 个位置找到值 5。
搜索字符串
slices.BinarySearchFunc 可以搜索字符串 slice。此示例执行不区分大小写的字符串比较。
package main
import (
"fmt"
"slices"
"strings"
)
func main() {
words := []string{"apple", "Banana", "cherry", "Date"}
cmp := func(a, b string) int {
aLower := strings.ToLower(a)
bLower := strings.ToLower(b)
switch {
case aLower == bLower:
return 0
case aLower < bLower:
return -1
default:
return 1
}
}
pos, found := slices.BinarySearchFunc(words, "banana", cmp)
fmt.Printf("Position: %d, Found: %v\n", pos, found)
}
比较函数首先将字符串转换为小写。这使得在查找“Banana”时搜索不区分大小写。
按字段搜索结构体
我们可以按特定字段搜索结构体 slice。此示例按年龄搜索人员。
package main
import (
"fmt"
"slices"
)
type Person struct {
Name string
Age int
}
func main() {
people := []Person{
{"Alice", 25},
{"Bob", 30},
{"Charlie", 35},
}
cmp := func(p Person, age int) int {
switch {
case p.Age == age:
return 0
case p.Age < age:
return -1
default:
return 1
}
}
pos, found := slices.BinarySearchFunc(people, 30, cmp)
fmt.Printf("Position: %d, Found: %v\n", pos, found)
}
比较函数会比较 Person 结构体的 Age 字段。它在第 1 个位置找到 Bob，他的年龄正好是 30 岁。
自定义排序
BinarySearchFunc 支持自定义排序方案。此示例按降序搜索。
package main
import (
"fmt"
"slices"
)
func main() {
numbers := []int{9, 7, 5, 3, 1} // Descending order
cmp := func(a, b int) int {
if a == b {
return 0
} else if a > b { // Note: reversed comparison
return -1
}
return 1
}
pos, found := slices.BinarySearchFunc(numbers, 5, cmp)
fmt.Printf("Position: %d, Found: %v\n", pos, found)
}
比较函数会颠倒标准的排序逻辑。这允许在降序排序的 slice 中进行搜索。
带有部分匹配的搜索
我们可以在比较中实现部分匹配。此示例在字符串 slice 中搜索前缀。
package main
import (
"fmt"
"slices"
"strings"
)
func main() {
words := []string{"apple", "application", "banana", "book"}
cmp := func(s, prefix string) int {
if strings.HasPrefix(s, prefix) {
return 0
} else if s < prefix {
return -1
}
return 1
}
pos, found := slices.BinarySearchFunc(words, "app", cmp)
fmt.Printf("Position: %d, Found: %v\n", pos, found)
}
比较使用 strings.HasPrefix 检查前缀匹配。它找到“app”的匹配项“apple”和“application”。
处理未找到的情况
当未找到目标时，该函数返回插入位置。此示例演示了如何处理缺失的元素。
package main
import (
"fmt"
"slices"
)
func main() {
numbers := []int{10, 20, 30, 40, 50}
cmp := func(a, b int) int {
if a == b {
return 0
} else if a < b {
return -1
}
return 1
}
pos, found := slices.BinarySearchFunc(numbers, 25, cmp)
if found {
fmt.Println("Found at position", pos)
} else {
fmt.Printf("Not found, would insert at %d\n", pos)
}
}
值 25 不在 slice 中，但将被插入到第 2 个位置。这会保持 slice 的排序顺序。
实际示例：字典查找
这个实际示例实现了字典查找。它在一个已排序的 slice 中搜索单词定义。
package main
import (
"fmt"
"slices"
)
type Entry struct {
Word string
Definition string
}
func main() {
dictionary := []Entry{
{"apple", "A fruit"},
{"banana", "Yellow fruit"},
{"cherry", "Small red fruit"},
}
cmp := func(e Entry, word string) int {
switch {
case e.Word == word:
return 0
case e.Word < word:
return -1
default:
return 1
}
}
pos, found := slices.BinarySearchFunc(dictionary, "banana", cmp)
if found {
fmt.Println("Definition:", dictionary[pos].Definition)
} else {
fmt.Println("Word not found")
}
}
比较函数按 Word 字段匹配 Entry 结构体。它有效地在已排序的字典 slice 中查找定义。
来源
本教程介绍了 Go 语言中的 slices.BinarySearchFunc 函数。我们通过自定义比较函数探索了各种搜索场景。