Dev Skills
Go·Go for coding rounds

Binary search, by hand and from the stdlib

Write it once without an off-by-one, then know when slices.BinarySearch and sort.Search do it for you.

Topic 28 of 98 · 5 min to read · 55 min to build
After this topic you can
  • Write an off-by-one-free binary search over an inclusive range.
  • Predict the lo, hi and mid values at each step for a small input.
  • Explain when sort.Search returns n and how to guard it.

The problem

Given a sorted slice and a target, return its index or -1. Follow-ups: "first element ≥ x", and "smallest k for which some condition holds" — binary search on the answer.

Brute force first

Linear scan: walk the slice from the left and return the first index where s[i] == target.

O(n) time, O(1) space. It works even on unsorted data, which is the only reason to keep it in mind.

The approach

Keep lo and hi as an inclusive range. Look at the middle; discard the half that cannot contain the target. O(log n) time, O(1) space. The input must be sorted — say so, and ask if it is.

For "first index where a condition becomes true", use sort.Search(n, f). It requires f to be false then true across the range, and returns n if it is never true.

bsearch.go
package main
import (
	"fmt"
	"slices"
	"sort"
)
// search returns the index of target in sorted s, or -1.
func search(s []int, target int) int {
	lo, hi := 0, len(s)-1
	for lo <= hi {
		mid := lo + (hi-lo)/2 // not (lo+hi)/2: that can overflow with 32-bit int
		switch {
		case s[mid] == target:
			return mid
		case s[mid] < target:
			lo = mid + 1
		default:
			hi = mid - 1
		}
	}
	return -1
}
func main() {
	s := []int{1, 3, 5, 7, 9, 11}
	fmt.Println(search(s, 7), search(s, 4)) // 3 -1
	// slices.BinarySearch: index where it is, or where it would go, plus found.
	i, found := slices.BinarySearch(s, 4)
	fmt.Println(i, found) // 2 false
	// sort.Search: the smallest i for which f(i) is true. The "lower bound"
	// tool, and the one to reach for in "first value >= x" problems.
	first := sort.Search(len(s), func(i int) bool { return s[i] >= 6 })
	fmt.Println(first, s[first]) // 3 7
	// Binary search on the answer: smallest k with k*k >= 50.
	k := sort.Search(100, func(k int) bool { return k*k >= 50 })
	fmt.Println(k) // 8
}

Dry run

s = [1 3 5 7 9 11], target = 9:

lohimids[mid]decision
05255 < 9, so lo = 3
3549found, return 4

Go-specific gotchas

  • `lo + (hi-lo)/2`, not (lo+hi)/2. lo+hi only overflows realistically when int is 32-bit (some ARM and WebAssembly targets) or the indices are huge. On 64-bit int it is rare, but the safe form costs nothing and interviewers look for it.
  • `slices.BinarySearch` returns `(index, found)`. When not found, the index is the insertion point, which is often what the follow-up wants.
  • `sort.Search` can return `n`. Check i < len(s) before you read s[i], or you panic on "not found".
  • Generic since Go 1.21. slices.BinarySearch works on any cmp.Ordered element type; use slices.BinarySearchFunc for structs.
The short version
  • Inclusive lo..hi, loop while lo <= hi, mid as lo + (hi-lo)/2.
  • slices.BinarySearch for exact lookups; sort.Search for lower bound and search-on-answer.
  • Always guard the "returned n" case.
Remember: Binary search works on any monotonic yes/no question, not only on sorted slices.
Build this before moving on
Find the first and last position of a target in a sorted slice with duplicates, using two sort.Search calls.
Coding challenge · checked by tests
Write search(s []int, target int) int that returns the index of target in the sorted slice s, or -1, in O(log n). Example: [1 3 5 7 9 11], 9 → 4.

Tab indents. Press Esc, then Tab, to leave the editor.

Then try these in your own editor
  1. 1The main task: Find the first and last position of a target in a sorted slice with duplicates, using two sort.Search calls.
  2. 2Use sort.Search to find the integer square root of 2,000,000,000 without math.Sqrt.
  3. 3Search a rotated sorted slice ([4 5 6 7 0 1 2]) for a target in O(log n).
  4. 4Dry run the hand-written search on s = [1 3 5 7 9 11] for target = 4. List lo, hi, mid each step and the final return value.
  5. 5Find the peak index in a "mountain" slice that strictly rises then falls ([1 3 8 12 4 2] → 3) in O(log n).
Official documentation
Check yourselfTake the Go for coding rounds test