Go语言二分查找与变种_Golang高效搜索算法实现-Golang-PHP中文网

sort.search 返回插入位置而非相等索引；正确用法是先用 a[i] >= target 找左边界，再判断 a[idx] == target。

go语言二分查找与变种_golang高效搜索算法实现

Go 语言里做二分查找，别自己从头写循环——sort.Search 是标准库给你的正确答案；但直接套用 sort.SearchInts 或手写递归容易返回错误索引或 panic，关键在理解它返回的是「插入位置」而非「是否存在」。

为什么 `sort.Search` 不等于“找相等”

sort.Search 的设计语义是：找到第一个满足条件的索引，不是“找 target 等于谁”。传入的函数必须返回 bool，且逻辑应为 a[i] >= target（升序前提下找左边界），而不是 a[i] == target。

常见错误现象：

sort.Search(len(a), func(i int) bool { return a[i] == target }) → 即使没找到，也可能返回中间某个索引，而该位置值 ≠ target
查 [1,3,5] 中的 4，返回 2（因为 a[2]==5 >= 4），但 a[2] != 4

正确做法是两步走：

先调 idx := sort.Search(len(a), func(i int) bool { return a[i] >= target })
再判断 idx 才算真正找到

`sort.SearchInts` 的隐藏限制与替代方案

sort.SearchInts 是 sort.Search 的快捷封装，只支持 []int 和升序，但它不校验输入是否真有序。一旦传入乱序切片，结果完全不可预测。

使用场景与注意事项：

仅适用于已确认升序的 []int；降序数组必须先反转或改用自定义 sort.Search
Go 1.21+ 推荐用 slices.BinarySearch（位于 slices 包），支持任意可比较类型，行为更直观：found, idx := slices.BinarySearch(a, target)
空切片安全：sort.Search(0, ...) 返回 0，不会 panic，但后续需检查 idx

手写迭代版二分：闭区间 `[left, right]` 最稳

自己写时，坚持用闭区间能大幅降低边界错误概率。循环条件是 left ，中点计算用 <code>left + (right - left) / 2 防整数溢出（虽对 int 少见，但属工程习惯）。

Golang Uber Dig

使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器，提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象，支持命名依赖等

下载

核心逻辑要点：

匹配时直接 return mid
arr[mid] > target → 缩右边界：right = mid - 1（mid 已排除）
arr[mid] → 缩左边界：<code>left = mid + 1（mid 已排除）
退出循环后必返回 -1，无需额外越界判断

示例片段：

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left  target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1
}