Binary Search in Go: Finding Data Fast
You have a sorted slice of integers representing transaction IDs. A new request comes in asking if ID 48291 exists. Scanning from the start works fine when the slice has ten elements. When the slice grows to a million elements, scanning every item wastes CPU cycles and adds latency. Binary search cuts the work in half with every step, turning a million checks into twenty.
How binary search works
Binary search works like guessing a number between one and a hundred. You don't count up from one. You guess fifty. If the answer is lower, you discard the top half and guess twenty-five. If higher, you discard the bottom half and guess seventy-five. Each guess eliminates half the remaining possibilities. With a hundred items, you find the target in seven guesses. With a billion items, you need thirty-one.
The algorithm relies on one invariant: the data must be sorted. If the data is unsorted, binary search returns nonsense. The implementation maintains two pointers, low and high. low starts at zero. high starts at the length of the slice. The loop calculates the middle index. If the middle element matches the target, the search stops. If the middle element is too small, the algorithm moves low past the middle, discarding the left half. If the middle element is too large, it moves high below the middle, discarding the right half. The loop continues until the pointers cross. When they cross, the target is not in the slice.
Binary search halves the problem. Sorted data is the price.
The modern API: slices.BinarySearch
Go 1.21 introduced the slices package with a straightforward API. slices.BinarySearch takes a sorted slice and a target value. It returns the index and a boolean indicating whether the value was found. The boolean flag removes the need for manual bounds checking in simple cases.
Here's the simplest usage: search a slice of integers and check the result.
package main
import (
"fmt"
"slices"
)
func main() {
// Sorted slice is a requirement; unsorted data breaks the algorithm
ids := []int{10, 20, 30, 40, 50}
// Returns index and found flag; handles empty slices safely
idx, ok := slices.BinarySearch(ids, 30)
if ok {
fmt.Printf("Found at index %d\n", idx)
} else {
fmt.Println("Not found")
}
}
The slices package arrived in Go 1.21 to consolidate slice operations. Before that, developers wrote helper functions or used third-party packages. The community now treats slices as the standard for slice manipulation. Use slices.BinarySearch for new code unless you need the predicate flexibility of sort.Search.
slices.BinarySearch returns a boolean. Trust the flag.
Step by step execution
The runtime behavior follows a predictable pattern. The function initializes low to zero and high to the slice length. The loop condition checks low < high. Inside the loop, the code computes the middle index. Go's standard library uses mid := low + (high-low)/2 to avoid integer overflow, though slice indices rarely reach the overflow threshold in practice.
The algorithm compares the element at mid with the target. If slice[mid] < target, the target must be in the upper half. The code sets low = mid + 1. If slice[mid] >= target, the target is in the lower half or at mid. The code sets high = mid. This narrowing continues until low equals high. At that point, low is the insertion point. The function checks if low is within bounds and if the element at low equals the target. If both are true, it returns the index and true. Otherwise, it returns the insertion point and false.
The loop shrinks the range. Pointers crossing means done.
Insertion points and missing values
When the target is not found, slices.BinarySearch and sort.Search return the index where the target would be inserted to keep the slice sorted. This is called the insertion point. If you are building a data structure that maintains a sorted list, the insertion point tells you exactly where to splice in a new element. This avoids a second search. You get the location in the same call that tells you the element is missing.
Consider a slice [10, 30, 50]. Searching for 20 returns index 1 and false. Index 1 is where 20 belongs. Searching for 60 returns index 3 and false. Index 3 is the length of the slice, meaning the target goes at the end. Searching for 5 returns index 0 and false. The target goes at the start.
The insertion point is free. Use it to maintain order.
Flexible search with sort.Search
Before Go 1.21, sort.Search was the standard. It remains useful for complex queries. sort.Search doesn't take a target value. It takes a length and a function that returns true when the element at index i is greater than or equal to the target. This predicate-based design lets you search by any criteria, not just equality. You can find the first element greater than a threshold, or search a struct by a specific field.
Here's how to search a slice of structs by timestamp using a predicate.
package main
import (
"fmt"
"sort"
)
// LogEntry represents a sorted log record
type LogEntry struct {
Timestamp int64
}
// findTimestamp locates the first entry at or after the threshold
func findTimestamp(logs []LogEntry, threshold int64) int {
// sort.Search expects a monotonic predicate: false, false, ..., true, true
// The function returns the first index where the predicate is true
idx := sort.Search(len(logs), func(i int) bool {
return logs[i].Timestamp >= threshold
})
// Verify the index is valid and the value matches exactly
if idx < len(logs) && logs[idx].Timestamp == threshold {
return idx
}
return -1
}
func main() {
logs := []LogEntry{{Timestamp: 100}, {Timestamp: 200}, {Timestamp: 300}}
fmt.Println(findTimestamp(logs, 200))
}
The predicate function passed to sort.Search must be monotonic. It must return false for all indices below the target and true for all indices at or above the target. If the predicate jumps back and forth, the result is undefined. This is a common source of subtle bugs. The function returns the insertion point, which is the index where the target would be placed to maintain sort order. If the target exists, the insertion point is the index of the first occurrence.
The predicate must be monotonic. A wobbly predicate breaks the search.
Custom comparators with slices.BinarySearchFunc
Go 1.21 also provides slices.BinarySearchFunc. This function takes a slice and a less function. It works like slices.BinarySearch but lets you define how elements compare. This is useful for structs where you want to search by a field but still use the modern slices API. The less function returns true if the first argument is less than the second.
Here's how to search a slice of users by ID using a custom comparator.
package main
import (
"fmt"
"slices"
)
type User struct {
ID int
Name string
}
func main() {
users := []User{
{ID: 1, Name: "Alice"},
{ID: 2, Name: "Bob"},
{ID: 3, Name: "Charlie"},
}
// BinarySearchFunc takes a less function to compare elements
// The less function returns true if the first argument is less than the second
idx, ok := slices.BinarySearchFunc(users, User{ID: 2}, func(a, b User) bool {
return a.ID < b.ID
})
if ok {
fmt.Printf("Found user %s at index %d\n", users[idx].Name, idx)
}
}
BinarySearchFunc bridges the gap. Define less, get the index.
Pitfalls and errors
Binary search assumes sorted data. Passing an unsorted slice produces incorrect results without a compiler error. The compiler cannot verify sort order at compile time. You get wrong answers, not a crash. Ensure the slice is sorted before searching. If you insert elements dynamically, maintain the sort order or re-sort before searching.
You cannot use slices.BinarySearch on a slice of structs directly. The function relies on the less-than operator to compare elements. Structs do not support comparison operators. The compiler rejects the code with invalid operation: a < b (operator < not defined on struct). Use sort.Search with a custom predicate for structs, or use slices.BinarySearchFunc with a less function.
Accessing the result index without bounds checking causes a panic. sort.Search returns the length of the slice when the target is greater than all elements. Reading slice[len(slice)] triggers panic: runtime error: index out of range. Always check idx < len(slice) before accessing the element. slices.BinarySearch mitigates this by returning a boolean flag, but you still need to check the flag before using the index.
Check bounds before indexing. The insertion point can be out of range.
When to use binary search
Use slices.BinarySearch when you have a slice of comparable primitives or types that support the less-than operator and you need an exact match.
Use sort.Search when you need to search by a custom predicate, such as finding the first element greater than a threshold or searching a struct by a specific field.
Use slices.BinarySearchFunc when you have a slice of structs and want to use the modern slices API with a custom comparison function.
Use sort.Search when targeting Go versions before 1.21 where the slices package does not exist.
Use a linear scan when the slice is small or unsorted; the overhead of binary search logic outweighs the benefit for fewer than twenty elements.
Use a map when you need frequent lookups by key; binary search requires sorted data and offers logarithmic lookup, while a map provides constant-time lookup without sorting constraints.
Pick the tool that matches your data shape. Don't force binary search on unsorted lists.