作为一个程序员，写bug不是什么丢脸的事。但是需要吃一堑长一智，不要在同样的地方再犯错误就行。

前言

二分查找，作为程序员再熟悉不过了。它是由John Mauchly在1946年第一次参加Moore School Lectures(电子计算机原理及技术课程)提出的。John自己在1986年发现他的二分查找算法中存在一个bug。

那么，这到底是个怎样的bug呢？大家可以先自己实现一个二分查找算法，看你会不会踩坑

二分查找

这里贴一段go版本的二分查找算法

// 二分查找，找第一个目标数字的下标，没有则返回-1
func binarySearch(arr []int64, target int64) int {
	if len(arr) == 0 {
		return -1
	}

	begin, end := 0, len(arr)-1
	for begin <= end {
		mid := (begin + end) / 2
		if arr[mid] > target {
			end = mid - 1
		} else if arr[mid] < target {
			begin = mid + 1
		} else {
			return mid
		}
	}

	return -1
}
复制代码

问题分析

乍一看好像没有问题，那问题究竟出在哪里呢？

这里涉及到计算机组成原理的知识。每个操作系统能表示的整形位数是有限的，超过这个位数的数字计算机是表示不出来的，说到这里，你再回头看看呢？是不是发现了问题？

没错，问题就出在 mid := (begin + end) / 2,这里mid大小就容易超过计算机的限制。

go语言int64最大能表示的数字是 (i<<63 – 1)

func main() {
	i1 := 1<<63-1
	i2 := 1
	mid := (i1+i2) / 2
	fmt.Println("i1=", i1)
	fmt.Println("i2=", i2)
	fmt.Println("mid=", mid)
}

结果：
i1= 9223372036854775807
i2= 1
mid= -4611686018427387904
复制代码

解决方法

既然加法不行，那就改成减法

func main() {
	i1 := 1<<63-1
	i2 := 1
	mid := i2 + (i1-i2) / 2
	fmt.Println("i1=", i1)
	fmt.Println("i2=", i2)
	fmt.Println("mid=", mid)
}

结果：
i1= 9223372036854775807
i2= 1
mid= 4611686018427387904
复制代码

扩展

其实这不算是算法的bug，算法本身没有问题，只是不同的计算机上不同的程序实现会产生bug。这种加法溢出的问题只要是两个数字相加都由可能出现溢出问题，所以大家在写程序的时候要注意，吃一堑长一智，才能不断地提升自己