Binary Search Go
Fast recall
Quick revision
Core answer
Whether you understand Binary Search Go beyond memorized syntax.
Giving a definition without explaining a practical trade-off.
Connect the concept to a small production example and state its complexity or failure mode.
Interview-ready guide
Interview answer
The implementation, executed:
func binarySearch(arr []int, target int) int {
lo, hi := 0, len(arr)-1
for lo <= hi {
mid := lo + (hi-lo)/2
if arr[mid] == target {
return mid
}
if arr[mid] < target {
lo = mid + 1
} else {
hi = mid - 1
}
}
return -1 // not found
}
// binarySearch([]int{1,3,5,7,9,11,13}, 7) → 3 — verified
// binarySearch([]int{1,3,5,7,9,11,13}, 8) → -1 — verifiedThe three details that matter:
- 1mid := lo + (hi-lo)/2 — NOT (lo+hi)/2 (the overflow-safe form — in Go's int it won't overflow, but the form is the standard)
- 2lo <= hi (the loop includes the single-element case — off-by-one is the classic binary search bug)
- 3lo = mid + 1 / hi = mid - 1 (the +/-1 — mid is already checked; excluding it guarantees termination)
The invariant: the target, if present, is always in [lo, hi]. Each iteration either finds it or strictly shrinks the range — the loop must terminate.
The prerequisite: the array MUST be sorted. Binary search on unsorted data is a random walk — correct by accident sometimes, wrong always.
The Go-specific note: sort.Search(n, f) is the standard library's general form — search the smallest i where f(i) is true over a sorted predicate. For simple lookups, sort.SearchInts / sort.SearchStrings are the direct calls.
Binary Search Go
Direct Answer
Sorted array, target, halve the range: mid, compare, adjust lo/hi. Returns the index or -1. O(log n). Verified: binarySearch([1,3,5,7,9,11,13], 7) = 3.
Deep Dive & Architecture
The loop invariants, formally: (1) if target is in the array, its index is always in [lo, hi]; (2) each iteration either returns or strictly decreases hi - lo. Together: termination with correctness. The off-by-one bugs are always violations of (1) or (2) — including mid in the next range (non-termination) or excluding the answer (missed finds).
The binary-search-on-answer pattern (the interview extension): when the PREDICATE is monotonic rather than the array — 'find the smallest capacity that works' — the same loop operates over the answer space. sort.Search(n, func(i int) bool { return feasible(i) }) is exactly this — the generalization that makes binary search a design tool, not just a sorted-array lookup.
The precision: the search does exactly ceil(log2(n+1)) comparisons in the worst case — for 1M elements, ~20 comparisons. The math: each comparison splits the remaining range in half; halving k times from n leaves n/2^k; the range hits 0 in k = log2(n) steps.
Common Mistakes & Pitfalls
Giving a definition without explaining a practical trade-off.
Check your understanding
Answer these without looking back at the article.
- When would you use Binary Search Go in a real project?
- How would you compare Binary Search Go with an alternative?
- What is a common mistake when using Binary Search Go?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.