Implementing Binary Search in Go

👋 Welcome Gophers! In this lesson, we are going to be implementing the Binary Search algorithm that we looked at in the previous lesson.

Implementation

Let’s start off by creating a new file called main.go within a new directory called 08-binary-search/. We’ll implement both iterative and recursive versions.

First, let’s create the iterative version of Binary Search:

package main

import "fmt"

// BinarySearch searches for a target value in a sorted slice
// Returns the index if found, or -1 if not found
func BinarySearch(arr []int, target int) int {
	left := 0
	right := len(arr) - 1

	for left <= right {
		mid := left + (right-left)/2

		if arr[mid] == target {
			return mid
		} else if arr[mid] < target {
			// Target is in the right half
			left = mid + 1
		} else {
			// Target is in the left half
			right = mid - 1
		}
	}

	// Target not found
	return -1
}

Now let’s create the recursive version:

// BinarySearchRecursive searches for a target value recursively
func BinarySearchRecursive(arr []int, target int) int {
	return binarySearchHelper(arr, target, 0, len(arr)-1)
}

// binarySearchHelper is a helper function for recursive binary search
func binarySearchHelper(arr []int, target int, left int, right int) int {
	if left > right {
		return -1
	}

	mid := left + (right-left)/2

	if arr[mid] == target {
		return mid
	} else if arr[mid] < target {
		return binarySearchHelper(arr, target, mid+1, right)
	} else {
		return binarySearchHelper(arr, target, left, mid-1)
	}
}

Now let’s test both implementations:

func main() {
	fmt.Println("Binary Search Algorithm in Go")

	// Create a sorted array
	arr := []int{5, 12, 18, 25, 31, 42, 50, 63, 75, 89}

	fmt.Println("Array:", arr)

	// Test iterative version
	target := 42
	index := BinarySearch(arr, target)
	if index != -1 {
		fmt.Printf("Iterative: Found %d at index %d\n", target, index)
	} else {
		fmt.Printf("Iterative: Target %d not found\n", target)
	}

	// Test recursive version
	index = BinarySearchRecursive(arr, target)
	if index != -1 {
		fmt.Printf("Recursive: Found %d at index %d\n", target, index)
	} else {
		fmt.Printf("Recursive: Target %d not found\n", target)
	}

	// Test with value not in array
	target = 100
	index = BinarySearch(arr, target)
	if index == -1 {
		fmt.Printf("Target %d not found (as expected)\n", target)
	}
}

Running this will output:

$ go run main.go
Binary Search Algorithm in Go
Array: [5 12 18 25 31 42 50 63 75 89]
Iterative: Found 42 at index 5
Recursive: Found 42 at index 5
Target 100 not found (as expected)

Using Go’s Built-in sort.Search

Go’s standard library provides the sort.Search function, which is a handy wrapper around binary search. Let’s see how to use it:

import (
	"fmt"
	"sort"
)

// Using Go's built-in binary search
func main() {
	fmt.Println("Using sort.Search")

	arr := []int{5, 12, 18, 25, 31, 42, 50, 63, 75, 89}
	target := 42

	// sort.Search returns the index where the element would be inserted
	// If the element exists, it will return its index
	index := sort.Search(len(arr), func(i int) bool {
		return arr[i] >= target
	})

	if index < len(arr) && arr[index] == target {
		fmt.Printf("Found %d at index %d\n", target, index)
	} else {
		fmt.Printf("Target %d not found\n", target)
	}
}

Handling Edge Cases

Let’s make sure our implementation handles edge cases:

func TestBinarySearchEdgeCases(t *testing.T) {
	// Test with single element
	arr := []int{42}
	if BinarySearch(arr, 42) != 0 {
		t.Error("Failed to find single element")
	}

	// Test with empty array
	arr = []int{}
	if BinarySearch(arr, 42) != -1 {
		t.Error("Should return -1 for empty array")
	}

	// Test with target not in array
	arr = []int{1, 3, 5, 7, 9}
	if BinarySearch(arr, 6) != -1 {
		t.Error("Should return -1 for target not in array")
	}

	// Test with target at beginning
	if BinarySearch(arr, 1) != 0 {
		t.Error("Failed to find element at beginning")
	}

	// Test with target at end
	if BinarySearch(arr, 9) != 4 {
		t.Error("Failed to find element at end")
	}
}

Finding Insertion Point

Another common use of binary search is finding where to insert a value to keep an array sorted:

// FindInsertionPoint finds where to insert target to keep array sorted
func FindInsertionPoint(arr []int, target int) int {
	left := 0
	right := len(arr)

	for left < right {
		mid := left + (right-left)/2
		if arr[mid] < target {
			left = mid + 1
		} else {
			right = mid
		}
	}

	return left
}

Performance Comparison

Let’s look at the performance benefits:

func main() {
	// Create a large sorted array
	arr := make([]int, 1000000)
	for i := 0; i < 1000000; i++ {
		arr[i] = i
	}

	target := 999999

	// Binary search is incredibly fast even on large datasets
	index := BinarySearch(arr, target)
	fmt.Printf("Found target at index: %d\n", index)

	// With 1 million elements, we only need ~20 comparisons!
}

Conclusion

Awesome! We now have a working implementation of the Binary Search algorithm in Go. We’ve covered iterative and recursive approaches, used Go’s standard library function, handled edge cases, and seen why binary search is so efficient on sorted data.

Quiz Time

Try your hand at these questions below to validate what we’ve just covered in this lesson: