Binary Search

One-liner: whenever a yes/no question flips from "no" to "yes" exactly once along an ordered range, you can find the flip point by repeatedly throwing away half the range.

The analogy

You are guessing a number from 1 to 100 and the friend only says "higher" or "lower". You never guess 1, 2, 3 — you guess 50, and each answer deletes half of the possibilities. After 7 guesses you are done. The key is not that the data is "a sorted array"; it is that each answer lets you discard a whole side.

Recognition signals

Reach for binary search when you see any of these:

1. The input is sorted (or sorted-then-rotated) and you need to find a position, a boundary, or a minimum.
2. The required complexity is O(log n), or n is so large (10^9 and up) that scanning is impossible.
3. The answer is a number you can test: "what is the smallest X such that this works?" and checking one X is easy. Bigger X never makes a working X stop working.

Step-by-step walkthrough

Take the sorted list 1, 3, 5, 7, 9, 11 and target 7. We look for the first index whose value is at least 7.

1. The live range is every index, lo = 0 up to (but not including) hi = 6.
2. Probe the middle, mid = 3, value 7. Is 7 >= 7? Yes. Index 3 might be the answer, so keep it and cut everything right of it: hi = 3.
3. Probe mid = 1, value 3. Is 3 >= 7? No. Index 1 and everything left of it is too small: lo = 2.
4. Probe mid = 2, value 5. No, so lo = 3.
5. lo == hi == 3: the range is empty and lo is the boundary. Check that nums[3] really equals 7.

Code template

Most off-by-one bugs come from inventing a new loop for every problem. Use one shape for everything: find the first index where a monotonic condition is true. Searching for a value, a lower bound, an upper bound and "search on answer" are all this same function with a different condition.

// firstTrue returns the smallest i in [0, n) with pred(i) == true, or n if none.
// pred must be monotonic: false, false, ..., true, true.
//
// Invariant: everything left of lo is false, everything at or right of hi is true.
// The answer is always in [lo, hi]. The range is half-open: hi itself is never probed.
func firstTrue(n int, pred func(i int) bool) int {
	lo, hi := 0, n
	for lo < hi {
		mid := lo + (hi-lo)/2 // lower middle, no overflow; mid < hi always
		if pred(mid) {
			hi = mid // mid might be the answer: keep it
		} else {
			lo = mid + 1 // mid is false: discard it
		}
	}
	return lo // lo == hi: the boundary
}

Why each part exists:

The invariant that holds before and after every iteration: everything left of lo is false, everything from hi on is true. If you can state that sentence about your loop, it is correct.

See it run

Watch the live range shrink. Cells outside [lo, hi) are dimmed — they have been proven irrelevant. Try the duplicates preset: the search lands on the first copy.

// Search: index of target in a sorted slice, or -1.
// Find the first index whose value is >= target, then check it really is target.
func Search(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
		}
	}
	if lo < len(nums) && nums[lo] == target {
		return lo
	}
	return -1
}

The classic search

// Search: index of target in a sorted slice, or -1.
// Find the first index whose value is >= target, then check it really is target.
func Search(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
		}
	}
	if lo < len(nums) && nums[lo] == target {
		return lo
	}
	return -1
}

It finds the first index with a value at least target, then makes one final check that the value is really there. Searching for an exact match inside the loop and returning early is the version that tends to break; this one cannot.

Variations

Lower and upper bounds — the first index with >= target and the first index with > target. Their difference is how many copies exist, and the second one minus one is the last occurrence:

// SearchRange: first and last index of target, or [-1, -1].
// Last occurrence = (first index with value > target) - 1.
func SearchRange(nums []int, target int) []int {
	first := firstTrue(len(nums), func(i int) bool { return nums[i] >= target })
	if first == len(nums) || nums[first] != target {
		return []int{-1, -1}
	}
	after := firstTrue(len(nums), func(i int) bool { return nums[i] > target })
	return []int{first, after - 1}
}

// SearchInsert: index where target is, or would be inserted.
func SearchInsert(nums []int, target int) int {
	return firstTrue(len(nums), func(i int) bool { return nums[i] >= target })
}

Search on the answer space — there is no array. Instead the candidates are the numbers 1 to the largest pile, and the condition is "can she finish in time at this speed?". Faster never hurts, so it is monotonic:

// MinEatingSpeed: smallest speed k so every pile is eaten within h hours.
// Search the ANSWER space [1, max(piles)]: "can finish at speed k" is false..false,true..true.
func MinEatingSpeed(piles []int, h int) int {
	maxPile := 0
	for _, p := range piles {
		maxPile = max(maxPile, p)
	}
	// candidate speed for index i is i+1
	i := firstTrue(maxPile, func(i int) bool {
		k, hours := i+1, 0
		for _, p := range piles {
			hours += (p + k - 1) / k // ceil(p / k)
		}
		return hours <= h
	})
	return i + 1
}

Same idea, different bounds. The smallest possible capacity is the heaviest package (anything lower can never ship it), and the largest useful one is the total weight:

// ShipWithinDays: least ship capacity that ships all packages in order within days.
// Capacity lies in [max(weights), sum(weights)]; "fits in days" is monotonic in capacity.
func ShipWithinDays(weights []int, days int) int {
	lo, total := 0, 0
	for _, w := range weights {
		lo = max(lo, w)
		total += w
	}
	i := firstTrue(total-lo+1, func(i int) bool {
		capacity := lo + i
		used, load := 1, 0
		for _, w := range weights {
			if load+w > capacity {
				used++
				load = 0
			}
			load += w
		}
		return used <= days
	})
	return lo + i
}

Rotated sorted array — the array is not sorted, but the condition nums[i] <= last element is false, false, true, true along it. That finds the minimum, i.e. the rotation point. Then search the array as if it were sorted using a shifted index:

// SearchRotated: target in a rotated sorted slice of distinct values, or -1.
// Step 1: find the rotation point (index of the minimum). Step 2: binary search the right half.
func SearchRotated(nums []int, target int) int {
	n := len(nums)
	if n == 0 {
		return -1
	}
	// the minimum is the first element that is <= the last element
	pivot := firstTrue(n, func(i int) bool { return nums[i] <= nums[n-1] })
	// treat the slice as sorted with a shifted index: real = (i + pivot) % n
	i := firstTrue(n, func(i int) bool { return nums[(i+pivot)%n] >= target })
	if i < n && nums[(i+pivot)%n] == target {
		return (i + pivot) % n
	}
	return -1
}

// FindMin: minimum of a rotated sorted slice of distinct values.
func FindMin(nums []int) int {
	n := len(nums)
	return nums[firstTrue(n, func(i int) bool { return nums[i] <= nums[n-1] })]
}

Complexity

Each iteration halves the range, so 10^9 candidates need only about 30 probes. For search-on-answer, the total cost is probes times the cost of one check.

Common mistakes

Practice ladder

Ordered Easy → Hard. Before coding, write the yes/no function and say out loud where it flips.

1. 1.
   Binary Search

   Sorted, and you want a position. What is the first index at least the target?
   Easy
2. 2.
   Search Insert Position

   The answer can be one past the end.
   Easy
3. 3.
   Find First and Last Position of Element in Sorted Array

   Two boundaries, two conditions.
   Medium
4. 4.
   Find Minimum in Rotated Sorted Array

   Compare each element with the last one.
   Medium
5. 5.
   Search in Rotated Sorted Array
   Medium
6. 6.
   Koko Eating Bananas

   There is no sorted input. What number is being guessed?
   Medium
7. 7.
   Capacity To Ship Packages Within D Days

   Bound the guess between the heaviest item and the total.
   Medium
8. 8.
   Median of Two Sorted Arrays

   Guess how many elements come from the first array.
   Hard

Which pattern? Drills

Unlabeled problems — pick the pattern, then read why.