Binary Search

Halve the range each step

Binary search keeps a window [lo, hi] of indices that could still hold the target. Look at the middle; if it’s too small, the answer must be to the right, so move lo past mid; if it’s too big, move hi before mid. Each step discards half the window, so n elements take about log₂(n) steps — 20 for a million.

graph TD
A["lo=0  hi=15  mid=7<br/>a[7] < target → go right"] --> B["lo=8  hi=15  mid=11<br/>a[11] > target → go left"]
B --> C["lo=8  hi=10  mid=9<br/>a[9] == target → found"]

The whole algorithm is one loop. The details that trip people up are all about boundaries: the loop condition and how you move lo and hi.

package main

import "fmt"

// binarySearch returns the index of target in the sorted slice a,
// or -1 if it is not present. Runs in O(log n).
func binarySearch(a []int, target int) int {
lo, hi := 0, len(a)-1 // inclusive window [lo, hi]
for lo <= hi {        // note: <=, so a one-element window is still checked
	mid := lo + (hi-lo)/2 // avoids lo+hi overflow on huge slices
	switch {
	case a[mid] == target:
		return mid
	case a[mid] < target:
		lo = mid + 1 // target is to the right; drop mid and left half
	default:
		hi = mid - 1 // target is to the left; drop mid and right half
	}
}
return -1
}

func main() {
a := []int{1, 3, 4, 7, 9, 11, 15, 22, 30, 41}
for _, target := range []int{7, 22, 8} {
	idx := binarySearch(a, target)
	fmt.Printf("search %2d -> index %d\n", target, idx)
}
}

The off-by-one traps

Three choices have to agree, or the loop spins forever or skips a value:

• Loop condition lo <= hi. With an inclusive window, lo == hi is a real one-element range you must still inspect. Using < instead would miss it.
• lo = mid + 1 and hi = mid - 1. You already compared mid, so exclude it. Writing lo = mid (without +1) when a[mid] < target leaves the window the same size and loops forever.
• mid := lo + (hi-lo)/2. Integer division rounds down, which keeps mid inside [lo, hi) when the window has two or more elements — exactly what the +1/-1 updates rely on.

Reach for the standard library

You rarely hand-roll this in production. The stdlib has two ready-made tools:

• slices.BinarySearch (Go 1.21+) — on an ordered slice it returns (index, found): the position if present, otherwise the index where the value would be inserted.
• sort.Search — the general form. You give it n and a predicate f(i) that is false … false true … true; it returns the first index where f is true. That’s the insertion point, so you check it yourself to confirm a real match.

This second form is the key idea: binary search isn’t only about slices. Any time you have a monotonic predicate — something that flips from false to true exactly once as a parameter grows — you can binary-search the smallest input that satisfies it. That’s “binary search on the answer”: instead of an index, you halve a numeric range (a speed, a capacity, a time) and probe the predicate at the midpoint.

package main

import (
"fmt"
"slices"
"sort"
)

func main() {
a := []int{1, 3, 4, 7, 9, 11, 15, 22, 30, 41}
target := 22

// slices.BinarySearch returns (index, found).
idx, found := slices.BinarySearch(a, target)
fmt.Printf("slices.BinarySearch: index=%d found=%t\n", idx, found)

// sort.Search returns the first index where the predicate is true,
// i.e. the first element >= target. Confirm the match yourself.
j := sort.Search(len(a), func(i int) bool { return a[i] >= target })
hit := j < len(a) && a[j] == target
fmt.Printf("sort.Search:         index=%d found=%t\n", j, hit)

// Both stdlib helpers agree with each other.
fmt.Printf("agree: %t\n", idx == j && found == hit)
}

See also

• sorting — the prerequisite; binary search needs ordered data.
• Big-O — O(log n), the canonical logarithmic algorithm.
• two pointers — the other sorted-data sweep.
• binary search trees — the same halving logic as a structure.

Next: how the slice gets sorted in the first place — sorting.

Related topics