7.1 Binary Search Template

Binary search is a boundary-finding algorithm. The common beginner description says that binary search finds an item in a sorted array, but that description is too narrow. The more useful version says this:

Given an ordered search space and a monotone predicate, binary search finds the first position where the predicate becomes true, or the last position where it remains false.

That framing covers exact lookup, lower bound, upper bound, insertion index, capacity planning, answer search, and many optimization problems.

Problem

You need a reliable binary search template that avoids off-by-one errors and works for most ordered search problems.

You have an array, a target value, and a monotone condition. You want to find the smallest index i such that the condition is true.

For example, in a sorted array:

nums = [2, 4, 4, 4, 7, 9]
target = 4

The lower-bound problem asks for the first index where nums[i] >= target. The answer is index 1.

Solution

Use a half-open interval [lo, hi). Keep lo as the first candidate position and hi as one past the last candidate position.

func LowerBound(nums []int, target int) int {
	lo, hi := 0, len(nums)

	for lo < hi {
		mid := lo + (hi-lo)/2

		if nums[mid] >= target {
			hi = mid
		} else {
			lo = mid + 1
		}
	}

	return lo
}

This function returns an insertion position. If the target exists, it returns the first occurrence. If the target does not exist, it returns the index where the target can be inserted while preserving sorted order.

nums := []int{2, 4, 4, 4, 7, 9}

fmt.Println(LowerBound(nums, 4))  // 1
fmt.Println(LowerBound(nums, 5))  // 4
fmt.Println(LowerBound(nums, 10)) // 6

The return value may equal len(nums). That means every element is smaller than the target.

Discussion

The half-open interval is the most stable template because it makes the loop boundary explicit. At the start, the search space is [0, len(nums)). The index lo is included. The index hi is excluded.

Each iteration chooses a midpoint:

mid := lo + (hi-lo)/2

This form avoids overflow in languages where lo + hi can exceed the integer limit. In Go on modern platforms this problem is less common for ordinary slices, but the safer formula costs nothing and keeps the template portable.

The key invariant is:

All indices before lo are known to be false.
All indices at or after hi are known to be true.
The unknown region is [lo, hi).

For lower bound, the predicate is:

nums[i] >= target

If nums[mid] >= target, then mid might be the first valid position, so you keep it by moving hi to mid.

hi = mid

If nums[mid] < target, then mid and everything before it cannot be the answer, so you remove them by moving lo to mid + 1.

lo = mid + 1

The loop ends when lo == hi. At that point, the unknown region is empty, and lo is the boundary between false and true.

Why This Template Works

Binary search succeeds because every iteration strictly shrinks the interval.

When nums[mid] >= target, the new interval is [lo, mid). The position mid is not lost as an answer because hi is exclusive. The candidate boundary remains represented by the value of hi.

When nums[mid] < target, the new interval is [mid + 1, hi). The midpoint is safely discarded because it fails the predicate.

This avoids the common bug where the loop keeps selecting the same midpoint forever. With [lo, hi), the update rules always remove at least one candidate from the unknown region.

Returning an Exact Match

Lower bound gives you the position where the target should be. To turn that into exact search, check the returned index.

func BinarySearch(nums []int, target int) int {
	i := LowerBound(nums, target)

	if i < len(nums) && nums[i] == target {
		return i
	}

	return -1
}

This returns the first matching index if the target exists. Otherwise, it returns -1.

fmt.Println(BinarySearch([]int{2, 4, 4, 4, 7, 9}, 4)) // 1
fmt.Println(BinarySearch([]int{2, 4, 4, 4, 7, 9}, 5)) // -1

This separation is useful. The lower-bound function solves the boundary problem. The exact-search function adds one final validation step.

Upper Bound

The upper-bound problem asks for the first index where nums[i] > target.

func UpperBound(nums []int, target int) int {
	lo, hi := 0, len(nums)

	for lo < hi {
		mid := lo + (hi-lo)/2

		if nums[mid] > target {
			hi = mid
		} else {
			lo = mid + 1
		}
	}

	return lo
}

For the same array:

nums := []int{2, 4, 4, 4, 7, 9}

fmt.Println(UpperBound(nums, 4)) // 4

The range of values equal to target is:

left := LowerBound(nums, target)
right := UpperBound(nums, target)
count := right - left

For target = 4, this gives [1, 4), so there are 3 occurrences.

Generic Boundary Search

Many problems have no array lookup at all. They only have a monotone predicate.

func FirstTrue(lo, hi int, ok func(int) bool) int {
	for lo < hi {
		mid := lo + (hi-lo)/2

		if ok(mid) {
			hi = mid
		} else {
			lo = mid + 1
		}
	}

	return lo
}

This searches the half-open range [lo, hi) and returns the first value for which ok is true.

Example: find the smallest integer x such that x*x >= n.

func CeilSqrt(n int) int {
	return FirstTrue(0, n+1, func(x int) bool {
		return x*x >= n
	})
}

This works for small integers, but x*x can overflow for large x. A safer version avoids multiplication overflow:

func CeilSqrt(n int) int {
	if n <= 1 {
		return n
	}

	return FirstTrue(1, n+1, func(x int) bool {
		return x >= (n+x-1)/x
	})
}

The expression (n+x-1)/x computes ceil(n / x) for positive integers, so the predicate means x >= ceil(n / x), which is equivalent to x*x >= n without directly multiplying.

Common Mistakes

The most common binary search bug is mixing interval conventions. If you start with [lo, hi), then hi is exclusive, the loop condition is lo < hi, and the true branch usually assigns hi = mid. If you start with [lo, hi], then hi is inclusive, the loop condition and update rules must change.

Another common bug is returning before validating. Lower bound returns an insertion position, not proof that the target exists. Always check i < len(nums) before reading nums[i].

A third common bug is assuming the returned index is always inside the array. For a target larger than every element, lower bound returns len(nums). That is a valid insertion position, but not a valid index for lookup.

Complexity

Binary search halves the unknown region on every iteration, so the number of iterations is logarithmic in the size of the search space.

For an array of length n, the time complexity is O(log n), and the space complexity is O(1).

For answer search over an integer range [lo, hi), the time complexity is O(log(hi - lo)) predicate evaluations. If the predicate costs T, the total cost is:

O(T log(hi - lo))

Takeaway

Use the half-open interval template as the default binary search pattern. Think in terms of a boundary, not an item. Define a monotone predicate, preserve the invariant that false values lie before lo and true values lie at or after hi, and return lo when the interval becomes empty.