函数
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, nfor i < j {h := int(uint(i+j) >> 1) // avoid overflow when computing h// i ≤ h < jif !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 = 3f(3) = arr[3] > 5 = falsei = 4 h = (i+j) / 2 = 5f(5) = arr[5] > 5 = truej = 5h = 4f(4) = arr[4] > 5 = falsei = 5,i == j return最后返回 5
