Introduction to Binary Search with Go

Welcome back to a new lesson! We're diving into Binary Search, a clever technique for locating specific elements within a sorted list. We can find the targeted item by repeatedly dividing the search interval in half. It's akin to flipping through a dictionary — instead of going page by page, you'd start in the middle, then narrow down the section in half until you find your desired word.

Binary Search begins at the midpoint of a sorted list, halving the search area at each step until it locates the target. For example, if you're looking for the number 8 in a sorted list ranging from 1 to 10, you would start at 5. Since 8 is larger than the midpoint, you narrow the search to the second half of the list, leaving you with numbers 6 to 10. In this new sublist, the middle number is 8, and thus, you've found your target. This efficient approach significantly reduces the number of comparisons needed compared to a linear search.

Let's see how Binary Search can be implemented in Go, taking a recursive approach. This involves a function calling itself — with a base case in place to prevent infinite loops — and a recursive case to solve smaller parts of the problem.

func BinarySearch(arr []int, start, end, target int) int {
    if start > end {
        return -1 // Base case
    }

    mid := start + (end-start)/2 // Find the midpoint

    if arr[mid] == target {
        return mid // Target found
    }

    if arr[mid] > target {
        return BinarySearch(arr, start, mid-1, target) // Search the left half
    }
    return BinarySearch(arr, mid+1, end, target) // Search the right half
}

In this Go code, the base case is defined first. If the start index is greater than the end index, it indicates the search area is exhausted, resulting in a -1 return. The code then locates the midpoint. If the midpoint equals our target, the index of the target element is returned. Depending on whether the target is less than or more than the midpoint, the search continues within the left or right half, respectively.

We can also visualize this search below:

[ 1 2 3 4 5 6 7 8 9 ] <- we want to find 3
|                   | <-the lines are the limits of our search
[ 1 2 3 4 5 6 7 8 9 ]
|       ^           | <- mid point is on 4
[ 1 2 3 4 5 6 7 8 9 ] <- 4 is larger than 3, ignore the left
|         |           <- our search area is cut in half!
[ 1 2 3 4 5 6 7 8 9 ]
|   ^    |            <- mid point is now 2
[ 1 2 3 4 5 6 7 8 9 ] <- 2 is smaller than 3, ignore the right
  |      |            <- our search area is cut again!
[ 1 2 3 4 5 6 7 8 9 ]
  |   ^  |            <- midpoint is now 3, out target!