Golang如何使用sort.Search进行二分查找-Golang-PHP中文网

Golang如何使用sort.Search进行二分查找

P粉602998670

发布： 2025-10-16 12:00:06

原创

984人浏览过

sort.Search通过二分查找在有序序列中定位首个满足条件的索引，适用于查找目标值、插入位置及左右边界。

golang如何使用sort.search进行二分查找

在Go语言中，sort.Search 是一个非常高效的内置函数，用于执行二分查找。它适用于已经排序的序列，能快速定位满足某个条件的第一个位置。理解其使用方式可以避免手动实现二分查找时的边界错误。

sort.Search 函数签名

func Search(n int, f func(int) bool) int

该函数在 [0, n) 范围内查找第一个使 f(i) 返回 true 的索引。如果不存在，则返回 n。关键在于传入的函数 f 必须是“单调递增”的：即存在一个位置 i，使得所有小于 i 的索引返回 false，从 i 开始及之后返回 true。

基本使用：在有序数组中查找目标值

假设我们有一个升序排列的整数切片，想要查找某个值是否存在，可以通过 sort.Search 找到第一个大于等于目标值的位置，再判断是否相等。

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

示例代码：

import (
    "fmt"
    "sort"
)
<p>func main() {
nums := []int{1, 3, 5, 7, 9}
target := 5</p><pre class='brush:php;toolbar:false;'>// 查找第一个 >= target 的位置
i := sort.Search(len(nums), func(i int) bool {
    return nums[i] >= target
})

// 判断是否找到且值相等
if i < len(nums) && nums[i] == target {
    fmt.Printf("找到 %d，索引为 %d\n", target, i)
} else {
    fmt.Printf("%d 未找到\n", target)
}

登录后复制

}

Rustic AI

AI驱动的创意设计平台

108

查看详情

查找插入位置（保持有序）

当目标值不存在时，sort.Search 可以用来确定应插入的位置，以维持切片的有序性。

例如，在 nums := []int{1, 3, 5, 7} 中插入 4：

i := sort.Search(len(nums), func(i int) bool {
    return nums[i] >= 4
})
// i == 2，表示应在索引 2 处插入 4
nums = append(nums, 0)
copy(nums[i+1:], nums[i:])
nums[i] = 4

登录后复制

查找范围：左边界和右边界

若数组中有重复元素，可以分别查找目标值的左边界和右边界。

左边界：第一个 >= target 的位置
右边界：第一个 > target 的位置，减 1 即为最后一个 target 的位置

示例：

left := sort.Search(len(nums), func(i int) bool { return nums[i] >= target })
right := sort.Search(len(nums), func(i int) bool { return nums[i] > target }) - 1

登录后复制

如果 left

基本上就这些。只要构造好判断函数，让其逻辑符合“前半段 false，后半段 true”的模式，就能正确使用 sort.Search。不需要手动写二分逻辑，简洁又安全。

以上就是Golang如何使用sort.Search进行二分查找的详细内容，更多请关注php中文网其它相关文章！