Golang切片.BinarySearch
最后修改于 2025 年 4 月 20 日
本教程将讲解如何在Go中使用slices.BinarySearch函数。我们将通过实际示例介绍在排序切片上进行二分查找操作。
slices.BinarySearch函数在排序切片中搜索目标值。它返回找到目标值的位置，或者它应该插入的位置。
二分查找的时间复杂度为O(log n)，效率很高。为了使函数正常工作，切片必须按升序排序。
基本的slices.BinarySearch示例
slices.BinarySearch最简单的用法是在排序切片中查找数字。该函数返回索引和布尔值，指示是否找到了该值。
package main
import (
"fmt"
"slices"
)
func main() {
numbers := []int{1, 3, 5, 7, 9}
index, found := slices.BinarySearch(numbers, 5)
fmt.Printf("Found: %v at index: %d\n", found, index)
}
我们创建一个排序好的切片并搜索值5。该函数返回索引2和true，因为5存在于切片中的该位置。
搜索不存在的值
当未找到目标时，slices.BinarySearch会返回它应该插入的位置。此示例演示了该行为。
package main
import (
"fmt"
"slices"
)
func main() {
numbers := []int{10, 20, 30, 40, 50}
index, found := slices.BinarySearch(numbers, 25)
fmt.Printf("Found: %v at index: %d\n", found, index)
}
切片中不存在值25。该函数返回索引2（介于20和30之间）和false。这对于插入点很有用。
搜索字符串
slices.BinarySearch也适用于字符串切片。此示例在排序列表中搜索姓名。
package main
import (
"fmt"
"slices"
)
func main() {
names := []string{"Alice", "Bob", "Charlie", "David"}
index, found := slices.BinarySearch(names, "Charlie")
fmt.Printf("Found: %v at index: %d\n", found, index)
}
字符串切片必须按字典序排序。“Charlie”在索引2处找到，因此函数返回true和该位置。
使用自定义类型
对于自定义类型，我们可以使用slices.BinarySearchFunc。此示例按年龄搜索结构体切片。
package main
import (
"cmp"
"fmt"
"slices"
)
type Person struct {
Name string
Age int
}
func main() {
people := []Person{
{"Alice", 25},
{"Bob", 30},
{"Charlie", 35},
}
index, found := slices.BinarySearchFunc(people, 30,
func(p Person, age int) int {
return cmp.Compare(p.Age, age)
})
fmt.Printf("Found: %v at index: %d\n", found, index)
}
我们提供一个比较函数，将Person.Age与我们的目标进行比较。该函数在年龄匹配30的索引1处找到Bob。
搜索浮点数值
由于精度问题，浮点切片需要谨慎处理。此示例显示了如何搜索浮点数。
package main
import (
"fmt"
"slices"
)
func main() {
values := []float64{1.1, 2.2, 3.3, 4.4, 5.5}
index, found := slices.BinarySearch(values, 3.3)
fmt.Printf("Found: %v at index: %d\n", found, index)
}
浮点切片必须按升序排序。该函数在索引2处正确找到3.3。请注意，浮点数比较可能因精度而变得棘手。
边缘情况
此示例探讨了空切片以及搜索第一个或最后一个元素等边缘情况。
package main
import (
"fmt"
"slices"
)
func main() {
empty := []int{}
numbers := []int{10, 20, 30}
// Empty slice
index, found := slices.BinarySearch(empty, 5)
fmt.Printf("Empty: %v at %d\n", found, index)
// First element
index, found = slices.BinarySearch(numbers, 10)
fmt.Printf("First: %v at %d\n", found, index)
// Last element
index, found = slices.BinarySearch(numbers, 30)
fmt.Printf("Last: %v at %d\n", found, index)
}
搜索空切片返回索引0和false。第一个和最后一个元素被正确处理，返回它们的真实索引。
实际示例：电话簿查找
这个实际示例演示了如何使用二分查找在排序的联系人列表中高效地查找电话号码。
package main
import (
"fmt"
"slices"
)
type Contact struct {
Name string
Phone string
}
func main() {
contacts := []Contact{
{"Alice", "555-0101"},
{"Bob", "555-0102"},
{"Charlie", "555-0103"},
{"David", "555-0104"},
}
// Sort by name
slices.SortFunc(contacts, func(a, b Contact) int {
if a.Name < b.Name {
return -1
}
return 1
})
// Search for Bob
index, found := slices.BinarySearchFunc(contacts, "Bob",
func(c Contact, name string) int {
if c.Name < name {
return -1
}
if c.Name > name {
return 1
}
return 0
})
if found {
fmt.Printf("Found %s: %s\n", contacts[index].Name,
contacts[index].Phone)
} else {
fmt.Println("Contact not found")
}
}
我们首先按姓名对联系人进行排序，然后搜索“Bob”。二分查找会快速找到联系人信息。这对于大型联系人列表来说非常高效。
来源
本教程通过实际示例，介绍了Go中的slices.BinarySearch函数，演示了在各种场景下对排序切片进行搜索。