Searching

Linear Search

Linear search checks each element in turn until it finds the target or runs out of elements. It needs no preparation and works on any slice, sorted or not, so it is the baseline every other method must beat.

The Scan

// linearSearch returns the index of target or -1. comparisons counts the
// work so it can be compared with binary search.
func linearSearch(a []int, target int) (idx, comparisons int) {
	for i, v := range a {
		comparisons++
		if v == target {
			return i, comparisons
		}
	}
	return -1, comparisons
}

The worst case, an absent target, costs n comparisons: O(n). In Go, slices.Index and slices.Contains are linear searches.

When Linear Search Is the Right Choice

Linear search wins when the data is small (a few dozen elements fit in cache and scan very fast), when it is searched only once, or when it changes constantly, so it cannot be kept sorted. It is also the only option when the question is not about order, for example "find the first user whose email is unverified". If you search the same data many times, sort it once, which costs O(n log n), or put it in a map, which costs O(n) to build.

Binary Search

If the slice is sorted, one comparison with the middle element tells you which half cannot contain the target. Discarding half of the range each step gives O(log n): one million elements need at most 20 comparisons, one billion at most 30. Full demo with a step-by-step trace, random cross-checks, and timings: 29_binary_search.go.

Searching for 40. Each step compares the middle element (orange) and discards the half that cannot hold the target (grey). When the range is empty, the target is absent.

Start from the Invariant

Choose a half-open range [lo, hi) and write down what must stay true: if the target is present, its index is in [lo, hi). Every line of the loop follows from that sentence:

• Start with lo = 0, hi = len(a): the whole slice.
• Loop while lo < hi: the range is not empty.
• If a[mid] < target, everything up to mid is too small, so lo = mid + 1.
• If a[mid] > target, everything from mid on is too large, so hi = mid. Because the range is half-open, mid is excluded.

// binarySearch uses the half-open range [lo, hi).
func binarySearch(a []int, target int) (idx, comparisons int) {
	lo, hi := 0, len(a) // invariant: target, if present, is in a[lo:hi]
	for lo < hi {       // the range is not empty
		mid := lo + (hi-lo)/2 // same as (lo+hi)/2 but cannot overflow
		comparisons++
		switch {
		case a[mid] < target:
			lo = mid + 1 // a[lo..mid] are all too small: discard them
		case a[mid] > target:
			hi = mid // a[mid..hi) are all too large: discard them
		default:
			return mid, comparisons
		}
	}
	return -1, comparisons
}

Why the Loop Terminates

A loop is correct only if it also finishes. While lo < hi, mid satisfies lo ≤ mid < hi, so both lo = mid + 1 and hi = mid make the range strictly smaller. Write lo = mid instead and a two-element range can stop shrinking, and the loop never ends. Computing mid as lo + (hi-lo)/2 avoids the overflow that (lo+hi)/2 can cause when indices are near the maximum integer, a bug that went unnoticed for years in several standard libraries.

Linear versus Binary in Numbers

The demo measures both methods for an absent target:

Binary search needs sorted input. Sorting first costs O(n log n), so it pays off only if you search the same data more than about log n times.

Lower and Upper Bounds

Most real questions are about positions, not presence: where would this value be inserted, how many values fall in a range, which is the first timestamp after noon. All of these reduce to one template. Demo with randomized checks against linear definitions: 30_search_bounds.go.

The First-True Template

Suppose a predicate over the indices is monotone: false, false, …, false, then true for every later index. Binary search finds the first true index in O(log n). The invariant is that the predicate is false before lo and true from hi onwards.

// firstTrue returns the smallest i in [0, n) with pred(i) true, or n if
// there is none. pred must be monotone: once true, true for every larger i.
func firstTrue(n int, pred func(int) bool) int {
	lo, hi := 0, n // invariant: pred is false before lo, true from hi on
	for lo < hi {
		mid := lo + (hi-lo)/2
		if pred(mid) {
			hi = mid // mid could be the answer: keep it in range
		} else {
			lo = mid + 1 // mid is false: the answer is to its right
		}
	}
	return lo // lo == hi: the boundary
}

lowerBound and upperBound

With the template, both bounds are one line each, and counting a value or a range becomes a subtraction:

func lowerBound(a []int, x int) int { // first index with a[i] >= x
	return firstTrue(len(a), func(i int) bool { return a[i] >= x })
}

func upperBound(a []int, x int) int { // first index with a[i] > x
	return firstTrue(len(a), func(i int) bool { return a[i] > x })
}

// a = [1 3 3 3 5 8 8 13]
// lowerBound(a, 3) = 1, upperBound(a, 3) = 4  -> 3 copies of 3
// lowerBound(a, 4) = 4 = upperBound(a, 4)     -> 4 is absent; insert at 4

lowerBound is also where a value should be inserted to keep a slice sorted: slices.Insert(a, lowerBound(a, x), x).

sort.Search and slices.BinarySearch

Go's standard library provides both forms. sort.Search(n, pred) is exactly firstTrue. slices.BinarySearch(s, x) returns the lower bound together with a flag that reports whether x is present, and slices.BinarySearchFunc does the same with a custom comparison. Prefer them in production code. Write the template yourself when the predicate is not a comparison with a slice element, as in the last section of this lesson.

Beyond Sorted Arrays

Binary search does not require fully sorted data. It requires a test on the middle element that tells you which half to discard.

Rotated Sorted Arrays

A sorted slice rotated at an unknown point, such as [15 18 22 3 7 9], still has one sorted half at every step. Check whether the target lies inside the sorted half's range; if not, it must be in the other half.

if a[lo] <= a[mid] { // left half is sorted
	if a[lo] <= target && target < a[mid] {
		hi = mid - 1
	} else {
		lo = mid + 1
	}
} else { // right half is sorted
	if a[mid] < target && target <= a[hi] {
		lo = mid + 1
	} else {
		hi = mid - 1
	}
}

This version uses a closed range [lo, hi] because it compares with a[hi]. Pick one convention per function and derive every boundary from it.

Finding a Peak

A peak is an element larger than both of its neighbours. In unsorted data you can still find one in O(log n): if a[mid] < a[mid+1], the values rise to the right, so they must either fall later or reach the end, and either way a peak exists on that side. The demo reuses firstTrue with the predicate a[i] > a[i+1].

Binary Search on the Answer

The most powerful use of binary search does not involve an array at all. Many optimization problems ask for the smallest value that works: the smallest ship capacity, the lowest speed, the shortest time. If "value x works" implies "every larger value works too", the candidate answers form a monotone false…true sequence, and you can binary search over them. Demo with a brute-force oracle: 31_search_the_answer.go.

The Recipe

1. Bound the answer: find a lo that is surely too small (or exactly minimal) and a hi that surely works.
2. Write feasible(x): usually a simple greedy pass in O(n).
3. Binary search for the first feasible value: O(n · log(hi − lo)).

Example: Shipping Capacity

Packages must ship in order within a given number of days. What is the smallest ship capacity that makes it? For a fixed capacity, a greedy pass counts the days needed. A larger ship never needs more days, so feasibility is monotone.

func shipWithinDays(weights []int, days int) int {
	lo := slices.Max(weights) // the heaviest package must fit
	hi := 0
	for _, w := range weights {
		hi += w // one day for everything always works
	}
	return firstFeasible(lo, hi, func(capacity int) bool {
		return daysNeeded(weights, capacity) <= days
	})
}

// daysNeeded is the greedy feasibility check: load each day until the next
// package does not fit. O(n).
func daysNeeded(weights []int, capacity int) int {
	d, load := 1, 0
	for _, w := range weights {
		if load+w > capacity {
			d++ // start a new day
			load = 0
		}
		load += w
	}
	return d
}

A brute-force solution tries every capacity. For a range of 10⁹ that is up to a billion feasibility checks; binary search needs 30.

Real-Valued Answers

When the answer is a real number (a cube root, a time, a rate), there is no "next integer". Run a fixed number of halvings instead: 100 iterations shrink any float64 range below its precision. Avoid a loop that runs while hi-lo > epsilon: for large values, floating-point rounding can keep the difference above epsilon forever.

Common Pitfalls

Almost every binary search bug is a boundary that does not match the invariant.

Mixing Half-Open and Closed Ranges

hi = len(a) with lo <= hi reads past the end; hi = len(a)-1 with lo < hi never examines the last element. Decide whether hi is inside or outside the range, write it in a comment, and check each update against it.

Updates That Do Not Shrink the Range

If an update can leave lo and hi unchanged, the loop spins forever on a two-element range. With mid = lo + (hi-lo)/2, assign lo = mid + 1, never lo = mid.

Searching Unsorted or Non-Monotone Data

Binary search on unsorted data compiles, runs, and returns wrong answers without any error. The same happens on the answer side when feasibility is not truly monotone. When in doubt, compare with a linear scan on random inputs, as every demo in this lesson does.

Practice Lab

For each problem, write the invariant or the monotone predicate before writing any code.

Run the Demos

1. In 29_binary_search.go, change hi = mid to hi = mid - 1 in binarySearch. Which invariant breaks, and how many random cross-checks fail?
2. In 30_search_bounds.go, make the same change in firstTrue and watch the bound checks fail.
3. In 31_search_the_answer.go, start shipWithinDays at lo := 1 instead of the heaviest package. Why does the oracle disagree? (Hint: what does daysNeeded do with a package heavier than the ship?)

Exercises

1. First and last position. Return the first and last index of a value in a sorted slice with duplicates, in O(log n).
2. Search a sorted matrix. Each row and column of a matrix is sorted. Find a value in O(rows + cols) by starting at the top-right corner. Why does that corner work?
3. Minimum in a rotated array. Find the smallest element of a rotated sorted slice with distinct values in O(log n).
4. Split array. Split a slice of positive integers into k contiguous parts that minimize the largest part sum. Write feasible(limit) and binary search on the limit.

Next: Sorting, which prepares data so binary search can be used.