二分查找

二分查找（又成折半查找），是一种在有序数组中查找特定元素的算法。

算法的时间复杂度是：O(logn)。

注意：该算法的前提是输入的数组必须是有序的，并且数组中的元素是可以比较的。

实现

这里以 Go 标准库的实现来演示，位置为 sort 包

// func GuessingGame() {
//		var s string
//		fmt.Printf("Pick an integer from 0 to 100.\n")
//		answer := sort.Search(100, func(i int) bool {
//			fmt.Printf("Is your number <= %d? ", i)
//			fmt.Scanf("%s", &s)
//			return s != "" && s[0] == 'y'
//		})
//		fmt.Printf("Your number is %d.\n", answer)
//	}
//
func Search(n int, f func(int) bool) int {
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1)
		if !f(h) {
			i = h + 1
		} else {
			j = h
		}
	}
	return i
}

在上述代码中：

• 数组的长度 n, 以及传入的回调函数 f， f 返回索引处的值是否与目标值相同。之所以传入一个回调函数 F 而不是特定数组，是因为 Go 目前的版本（1.17) 还不支持泛型，所以为了支持不同类型的数组查找，需要使用闭包函数来获取特定位置值，正如注释代码所示。并且， 定义 f(-1) == false and f(n) == true.

• 创建两个变量，指向当前查找范围的头尾，j = n 是为了处理目标元素刚好在切片尾部的情况

• 当查找范围的左边界面小于右边界时，进行下面的操作

• 选择当前范围中部的值，使用 int(uint(i+j) >> 1) 而非 (i + j) / 2 获取中间索引的原因是为了防止整数越界

• 将中间位置的值与目标值比较，如果小于目标值，说明目标值在右半部区域，移动左边界。反之则说明在左部区域中，需要移动右边界。循环处理，只到中间位置的值等于目标值，或者遍历完所有元素后退出循环

• 最后返回结果 i，由于 i == j, f(i-1) == false, and f(j) (= f(i)) == true 所以答案是 i 。如果目标元素不存在，i = n, 越界，所以需要判断最后的结果是否为合法索引值。

使用场景

1. 在目标序列中查找特定值（需要预先排序）
2. 将目标值插入有序列时，获取对应的索引