Binary Search in Go

Binary Search is a fundamental searching algorithm that you can use to find a number in a sorted array. The general idea is, since the array is sorted, you can check the value of the middle element, see if the value you're looking for is less than it or greater than it, and depending on which it is, eliminate the half of the array that you don't need from your search and check the other half where it should exist. You keep doing that, reducing the search area by half each time until you either find the value or come up empty.

This means we can search really large lists (again, they have to be sorted for this to work) and we can feasibly find a value with much less effort than checking every number sequentially, or even worse, randomly guessing. For example, if we started with a list that had 32 values, we'd go from searching:

32 -> 16 -> 8 -> 4 -> 2 -> 1

That's only a maximum of 6 iterations! Not bad compared to a possible 32, but it's even crazier when you think about larger numbers, for example, let's say... 32,768:

32,768 -> 16,384 -> 8,192 -> 4,096 -> 2,048 -> 1,024 -> 512 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

That's still only a maximum of 16 iterations. MUCH better than potentially checking each number in the list.

So let's look at how to implement this in Go. First, we want to define two "pointers" that will be the endpoints of the section we search in. Of course we start by searching the entire list, so our 'left' boundary will be the first element in the array and the 'right' boundary will be the last one. Then we start our loop. Every time it runs, we first calculate the midpoint index of the list and get that element. Then we check to see if the value at that index is the one we're looking for and return it if it is. If not, we check to see if it's less than the midpoint. If so, we 'slide in' the right boundary to the midpoint so we're only focusing on the side with all the numbers less than it. On the other hand, if it's greater than the midpoint, we 'slide up' the left boundary so we're only looking at the half with values greater than the midpoint. Then we loop again and the same thing continues, cutting the search window in half each time until we either find the target value or exit the loop without finding it. If we don't find it, we just return -1 signifiying that the value is not in the list.

So for example if we had the following list, and were looking for 20, our searching would look like this:

1, 3, 4, 6, 7, 8, 9, 11, 12, 15, 17, 20, 50
^                                         ^
0                                         12

there are 13 numbers in the list, so 12 / 2 gives us 6. The number at index 6 is 9

1, 3, 4, 6, 7, 8, 9, 11, 12, 15, 17, 20, 50
^                 ^                      ^
0                 6                      12

9 is not equal to 20, so we ask is 20 greater than 9 or less? since it's greater, we 'slide up' the left boundary to 1 past our midpoint

1, 3, 4, 6, 7, 8, 9, 11, 12, 15, 17, 20, 50
                     ^                   ^
                     7                   12

then check the midpoint of this smaller window, (12 - 7) / 2 + 7 = 9

1, 3, 4, 6, 7, 8, 9, 11, 12, 15, 17, 20, 50
                     ^       ^           ^
                     7       9           12

the value at index 9 is 15. 15 =/= 20, but 20 is greater than 15, so we slide up the left boundary 1 past the new midpoint

1, 3, 4, 6, 7, 8, 9, 11, 12, 15, 17, 20, 50
                                 ^       ^
                                 10      12

then check the midpoint, (12 - 10) / 2 + 10 = 11

1, 3, 4, 6, 7, 8, 9, 11, 12, 15, 17, 20, 50
                                 ^   ^   ^
                                 10  11  12

the element at index 11 is 20 and since 20 == 20 So we've found our element at index 11

we can exit the loop and return 11

First, let's see how to implement it iteratavely.

func BinarySearch(sl []int, elem int) int {
	var start int = 0
	var end int = len(sl) - 1

	for start <= end {
		midpoint := start + (end-start)/2
		if elem == sl[midpoint] {
			return midpoint
		}

		if elem < sl[midpoint] {
			end = midpoint - 1
		} else {
			start = midpoint + 1
		}
	}

	return -1
}

Now let's look at an example of doing the same thing via recursion instead of iteratively. The main difference here is that we have to initially call this function by passing in the left and right boundaries and every time we recursively call it, we do on the half of that we need to search next. We just keep calling it until our window shrinks to nothing or we find the number:

func BinarySearchRecursive(sl []int, elem int, start int, end int) int {
	if start > end {
		return -1
	}
	midpoint := start + (end-start)/2
	if elem == sl[midpoint] {
		return midpoint
	}
	if elem < sl[midpoint] {
		return BinarySearchRecursive(sl, elem, start, midpoint-1)
	} else {
		return BinarySearchRecursive(sl, elem, midpoint+1, end)
	}
}

Since we're halving the time needed to complete this task on every iteration, the time complexity is O(logn). One other point worth mentioning, you might initially try to jump in and write the code for this problem by creating a new sub-array on each iteration. That would technically allow you to find the value if it exists, but you'd be using a bunch of unnecessary memory creating all those extra arrays when you should just leave the one you have in place and shrink the search window on it. That keeps the space complexity O(1). Also, this let's you easily return the index of the element at exactly where it exists in the array.

One last thing to note, is that binary search isn't only for numbers either. The values in the array just need to be monotonic, which means they generally move in one direction. An example of monotonic values aside from numbers are booleans. If you had a list of trues and falses where all the trues were on one side and all the falses were on the other, you could use binary search to find the first occurrence of one or the other. So for example, if we're looking for the first occurrence of false:

// there are 10 values in the list, so 9 / 2 gives us 4 via integer division
// and the value at index 4 is T

|T, T, T, T, T, F, F, F, F, F|
             ^
             4

// T =/= F
// so the F must be on the right half
// we 'slide up' the left boundary to index 4
// then check the midpoint, (9 - 4) / 2 + 4 = 6

T, T, T, T, |T, F, F, F, F, F|
                   ^
                   6

// the value at index 6 is F. F == F
// since we found an F, we know that either index 6
// or something to the left of it is the first F 
// so we slide up the right boundary to index 7 (1 after 7)

T, T, T, T, |T, F, F, |F, F, F
                   ^
                   6

// then check the midpoint, (7 - 4) / 2 + 4 = 5
// the value at index 5 is F. F == F

T, T, T, T, |T, F, F, |F, F, F
                ^
                5

// since we found another F, we know that either index 5
// or something to the left of it is the first F 

T, T, T, T, |T, F,| F, F, F, F
                ^
                5

// then check the midpoint, (5 - 4) / 2 + 4 = 4

T, T, T, T, |T, |F, F, F, F, F
             ^
             4

// since the element at index 4 is a T, and it's the last thing in the list,
// the element to the right of it, index 5 is the first F

And that's pretty much it for Binary Search in Go. It's a simple but powerful search algorithm that you can use whenever you have an array of values that are already sorted and are monotonic.