As a programmer, there is no shame in writing bugs. But you need to learn from the mistakes and not make the same mistakes in the same place.

preface

Binary search, as a programmer is all too familiar. It was proposed by John Mauchly in 1946 when he attended Moore School Lectures(electronic Computer Principle and Technology course) for the first time. John himself discovered a bug in his binary search algorithm in 1986.

So, what kind of bug is this? You can first implement a binary search algorithm, see if you will step on the pit

Binary search

Here’s a clip of go’s binary search algorithm

// Binary search, find the first target number subscript, if no -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
}
Copy the code

Problem analysis

At first glance, there seems to be no problem, but what is the problem?

This involves knowledge of how computers are made up. Each operating system can represent a limited number of plastic digits, more than this number is not represented by the computer, said here, you look back? Did you find a problem?

The problem is that mid = (begin + end) / 2, where mid tends to exceed the computer’s limit.

The largest number that the GO language int64 can represent is (I << 63-1)

func main(a) {
	i1 := 1<<63- 1
	i2 := 1
	mid := (i1+i2) / 2
	fmt.Println("i1=", i1)
	fmt.Println("i2=", i2)
	fmt.Println("mid=", mid)9223372036854775807
i2= 1
mid= - 4611686018427387904.
Copy the code

The solution

Since addition doesn’t work, let’s change to subtraction

func main(a) {
	i1 := 1<<63- 1
	i2 := 1
	mid := i2 + (i1-i2) / 2
	fmt.Println("i1=", i1)
	fmt.Println("i2=", i2)
	fmt.Println("mid=", mid)9223372036854775807
i2= 1
mid= 4611686018427387904
Copy the code

extension

In fact, this is not a bug of the algorithm, there is nothing wrong with the algorithm itself, just different implementation of the program on different computers can cause bugs. This kind of addition overflow problem as long as the addition of two numbers by the overflow problem may occur, so we should pay attention to when writing the program, a fall into the pit and a gain in your wisdom, in order to constantly improve themselves