go sort.Search()

2023-12-13 16:13:39

函数

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

函数作用

通过二分法查找,找到已经排序好的数组[0,n)中第一个使f为true的索引,如果没有找到返回n

为什么要用二分查找?
因为二分查找相比普通依次遍历而言,速度能有巨幅提升。就好比你查字典的时候,你是会从头往后一页一页的翻,还是会直接翻开中间某页,再翻开中间的中间的某页。二分查找相比于依次遍历查找而言,将时间复杂度从O(n)变为了O(log(n))

在这里插入图片描述

使用示例

下面进行了演示

func main() {
	arr := []int{1, 2, 3, 4, 5, 6, 7}
	i := sort.Search(len(arr), func(i int) bool {	// 返回 arr[0,7)中第一个满足arr[i]>5 的索引
		return arr[i] > 5
	})
	fmt.Println(i)	//i:5
}

源码分析

源码位于sort包下

func Search(n int, f func(int) bool) int {
	// Define f(-1) == false and f(n) == true.
	// Invariant: f(i-1) == false, f(j) == true.
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // avoid overflow when computing h
		// i ≤ h < j
		if !f(h) {
			i = h + 1 // preserves f(i-1) == false
		} else {
			j = h // preserves f(j) == true
		}
	}
	// i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
	return i
}
for i < j {
	...
}
return i

有效索引范围为[0,n),当 i >= j 时结束

h := int(uint(i+j) >> 1)

位运算,将i、j的和转化为二进制右移(删除)一位,等价于(i+j)/ 2。h表示中间索引 i ≤ h < j
比如十进制5经过 >> 1 结果为 2。
在这里插入图片描述

if !f(h) {
		i = h + 1 // preserves f(i-1) == false
} else {
		j = h // preserves f(j) == true
}

以上面的示例为例

i = 0 ,j = 7 , h = 3

f(3) =  arr[3] > 5 = false

i = 4 

h = (i+j) / 2 = 5

f(5) = arr[5] > 5 = true

j = 5

h = 4

f(4) = arr[4] > 5 = false

i = 5,i == j return

最后返回 5

文章来源:https://blog.csdn.net/Wksycxy/article/details/134891015
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。