Go sort.Search()和sort.Find()
sort.Search()
sort.Search() 提交于遥远的2010年11月11日,提交者是Go三位创始人之一的Robert Griesemer[1], 随Go第一个正式版本一起发布
从这个意义上说,是标准库元老级的函数了~
sort.Search()[2] 用于在排序的切片或数组中查找元素
// Search uses binary search to find and return the smallest index i
// in [0, n) at which f(i) is true, assuming that on the range [0, n),
// f(i) == true implies f(i+1) == true. That is, Search requires that
// f is false for some (possibly empty) prefix of the input range [0, n)
// and then true for the (possibly empty) remainder; Search returns
// the first true index. If there is no such index, Search returns n.
// (Note that the "not found" return value is not -1 as in, for instance,
// strings.Index.)
// Search calls f(i) only for i in the range [0, n).
//
// A common use of Search is to find the index i for a value x in
// a sorted, indexable data structure such as an array or slice.
// In this case, the argument f, typically a closure, captures the value
// to be searched for, and how the data structure is indexed and
// ordered.
//
// For instance, given a slice data sorted in ascending order,
// the call Search(len(data), func(i int) bool { return data[i] >= 23 })
// returns the smallest index i such that data[i] >= 23. If the caller
// wants to find whether 23 is in the slice, it must test data[i] == 23
// separately.
//
// Searching data sorted in descending order would use the = operator.
//
// To complete the example above, the following code tries to find the value
// x in an integer slice data sorted in ascending order:
//
// x := 23
// i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
// if i
1) // avoid overflow when computing h
// i ≤ h
answer is i.
return i
}
这段代码是一个实现了二分查找算法的函数，名为 Search。这个函数用于在一个有序的范围内寻找满足特定条件的最小索引 i。以下是对这个函数的详细解释：
-
函数定义：Search(n int, f func(int) bool) int 定义了一个名为 Search 的函数，接收两个参数：一个整数 n 和一个函数 f。n 定义了搜索范围的大小（从 0 到 n，不包括 n），而 f 是一个接受整数输入并返回布尔值的函数。Search 函数返回一个整数，表示满足 f 条件的最小索引。
-
**条件函数 f**：f 函数定义了查找的条件。对于索引 i，如果 f(i) 为真，则对于所有 j > i，f(j) 也应为真。这意味着 f 在某点之前为假，之后变为真。Search 函数查找的是这个转变发生的点。
-
二分查找逻辑：
- 初始化两个指针 i 和 j，分别代表搜索范围的开始和结束。开始时， i 为 0， j 为 n。
- 在 i
- 如果 f(h) 为假（ false），则说明满足条件的索引在 h 的右侧，将 i 设置为 h + 1。
- 如果 f(h) 为真（ true），则说明满足条件的索引可能是 h 或在 h 的左侧，将 j 设置为 h。
- 这个过程不断缩小搜索范围，直到找到转变点，即 f(i-1) 为假而 f(i) 为真的位置。
-
结果返回：当 i 与 j 相遇时，i 就是满足 f(i) 为真的最小索引。如果整个范围内没有找到满足条件的索引，则返回 n。
这个 Search 函数的一个常见用途是在有序数组或切片中查找一个元素或查找满足某个条件的元素的插入点。例如，如果你有一个按升序排序的数组，并想要找到第一个大于等于某个值 x 的元素的索引，你可以将 x 的值和数组索引作为条件传递给 f 函数，并使用 Search 函数来查找。
这种类型的二分查找算法非常高效，时间复杂度为 O(log n)，适用于大型数据集合。二分查找不仅可以用于查找元素，还可以用于确定元素的插入位置，以保持数据的有序性。
会在一个已排序的切片中进行二分查找(因此比线性搜索要快得多，尤其是在处理大型数据集时性能尤其明显), 最后返回一个索引，这个索引指向切片中第一个不小于指定值的元素。如果没有找到符合条件的元素，则返回的索引等于切片的长度。
使用时首先需要确保切片或数组已经是排序过的。其次需提供一个函数，这个函数定义了怎样判断切片中的元素是否满足自定义的查找条件。
如下,假设有一个整数切片，已经按升序排序，想找到第一个不小于某个给定值的元素的位置。
package main
import (
"fmt"
"sort"
)
func main() {
// 已排序的切片
numbers := []int{1, 2, 4, 6, 8, 10}
// 要查找的值
target := 5
// 使用 sort.Search
index := sort.Search(len(numbers), func(i int) bool {
return numbers[i] >= target
})
// 输出结果
if index
