Golang sort/search切片二分查找实践-Golang-PHP中文网

Golang sort/search切片二分查找实践

P粉602998670

发布： 2025-09-22 18:38:01

原创

736人浏览过

在Go中对切片进行二分查找需确保数据有序，sort包提供sort.Search实现灵活查找，通过条件函数定位首个不小于目标的索引，结合预定义函数如sort.SearchInts、sort.SearchStrings可简化操作，还可利用插入点保持有序。

golang sort/search切片二分查找实践

在Go语言中，对切片进行二分查找时，必须保证数据已排序。标准库

sort

登录后复制

提供了高效且类型安全的工具，能快速实现查找、插入等操作。以下是实际使用中的常见场景和方法。

使用 sort.Search 进行自定义二分查找

sort.Search

登录后复制

是最灵活的方式，适用于任意有序切片。它接受长度 n 和一个判断条件 f(i)，返回满足 f(i) 为 true 的最小索引。

例如：在一个升序整数切片中查找目标值的位置：

func binarySearch(arr []int, target int) int {
    i := sort.Search(len(arr), func(i int) bool {
        return arr[i] >= target
    })
    if i < len(arr) && arr[i] == target {
        return i
    }
    return -1 // 未找到
}

登录后复制

这个写法的关键在于条件函数

arr[i] >= target

登录后复制

，它定位第一个不小于目标值的位置，再通过额外判断确认是否相等。

使用预定义函数简化查找

对于常见类型，

sort

登录后复制

包提供了专用函数，代码更简洁：

立即学习“go语言免费学习笔记（深入）”；

宣小二

宣小二：媒体发稿平台，自媒体发稿平台，短视频矩阵发布平台，基于AI驱动的企业自助式投放平台。

查看详情

```
sort.Ints(arr)
```
登录后复制
—— 对整型切片排序
```
sort.Strings(arr)
```
登录后复制
—— 对字符串切片排序
```
sort.SearchInts(arr, x)
```
登录后复制
—— 在已排序整型切片中查找 x
```
sort.SearchStrings(arr, x)
```
登录后复制
—— 在已排序字符串切片中查找 x

示例：快速查找字符串是否存在

names := []string{"Alice", "Bob", "Charlie"}
sort.Strings(names)
index := sort.SearchStrings(names, "Bob")
if index != len(names) && names[index] == "Bob" {
    fmt.Println("Found at", index)
}

登录后复制

插入新元素并保持有序

利用

sort.Search

登录后复制

找到插入点，可将新元素放入正确位置而不破坏顺序。

比如向有序整数切片插入一个数：

func insertSorted(arr []int, x int) []int {
    i := sort.Search(len(arr), func(i int) bool { return arr[i] >= x })
    arr = append(arr, 0)
    copy(arr[i+1:], arr[i:])
    arr[i] = x
    return arr
}

登录后复制

这段代码先用