Binary Search

What Binary Search Actually Does

A linear scan checks each element and learns nothing from each comparison that helps skip later elements. If the target is at the end, every element before it is examined.

Binary search eliminates half the candidates with each comparison. When arr[mid] < target in a sorted array, every index to the left of mid also holds a value less than target. The comparison proves that the entire left half cannot contain the answer, so the search discards it.

This is the exact search form. It returns the moment it finds target, or -1 if target is absent. But many problems need something different: finding the first occurrence, the insertion point, or the boundary where some condition changes. Those require a different form.

How the Search Space Shrinks

Binary search maintains an invariant: if the answer exists, it lies within [left, right]. Each comparison proves that half the remaining elements cannot be the answer, allowing them to be discarded. Every update to left or right must preserve this invariant.

The real requirement for binary search is not a sorted array. It is a monotonic decision structure: a condition that transitions from false to true (or vice versa) as the search space is traversed. Binary search finds the transition point. Sorting is one way to create this structure, but not the only way.

Three Kinds of Search Space

Index space. The answer is a position in an array. The search space is [0, n-1] or [0, n). Problems like "find target in sorted array" and "find peak element" fall here. The giveaway is that the problem provides an array and asks for a position.

Value space. The answer is a numeric value, not an index. The search space is [min_possible, max_possible]. Integer square root and "find smallest divisor" are value space problems. The giveaway is that the problem asks for a value satisfying some constraint, not a position.

Answer space. The answer is the optimal value of some objective. The search space is the range of possible answers to the optimization. Koko eating bananas, split array largest sum, and capacity to ship packages all fit this category. The giveaway is phrasing like "minimize the maximum" or "maximize the minimum." For each candidate answer, a feasibility function determines whether that answer is achievable.

First Walkthrough

Before learning the forms, trace through a concrete example to see how the search space shrinks. The animation below searches for target = 9 in [1, 3, 5, 7, 9, 11, 13, 15].

At each step, the comparison proves that half the remaining elements cannot be the target. When arr[mid] is less than 9, sorted order guarantees every element left of mid is also less than 9, so the left half is safely discarded. The search space shrinks from 8 to 4 to 2 to 1. Found in 3 comparisons. A linear scan of 8 elements could need 8.

Form 1: Exact Search

Exact search looks for a specific value that may or may not exist. The loop terminates either when the target is found (return immediately) or when zero candidates remain (target absent, return -1).

Why right = len(arr) - 1? The search space is inclusive on both ends. Index len(arr) does not exist, so len(arr) - 1 is the last valid index.

Why left <= right? The search space [left, right] represents all indices that remain valid candidates. When left equals right, there is exactly one index remaining that has not been examined. If you used left < right instead, the loop would exit the moment left equals right, skipping that final candidate entirely.

Why mid - 1 and mid + 1? After checking arr[mid], that index is either the answer (return immediately) or definitely not the answer (exclude it). Moving to mid ± 1 excludes the checked element.

Form 2: Lower Bound

Lower bound finds the first position where arr[i] >= target. When target exists, this is the first occurrence. When target is missing, this is where it would be inserted to maintain sorted order. This form treats the search space as [left, right) where left is inclusive and right is exclusive.

Why right = len(arr)? The boundary might be past the end. If all elements are less than target, the insertion point is index len(arr). This must be a valid answer, so the search space must include it.

Why left < right (not <=)? When left == right, the search space [left, right) is empty. No candidates remain. The boundary is at index left.

Why right = mid (not mid - 1)? When arr[mid] >= target, mid might BE the boundary (the first element >= target). Setting right = mid shrinks the space but keeps mid reachable. When the loop terminates with left == right, that index is the boundary. Using mid - 1 would skip past the boundary entirely.

When arr[mid] equals target, you found a match, but possibly not the first one. The condition arr[mid] < target is false, so the else branch runs: right = mid. This keeps mid as a candidate while continuing leftward. The search keeps going left until left meets right at the leftmost occurrence.

Form 3: Upper Bound

Upper bound finds the first position where arr[i] > target. When target exists, this lands one position after the last occurrence. Use upper bound when you need "last occurrence" (subtract 1 from the result) or "count of target" (upper minus lower).

When arr[mid] equals target, upper bound wants to get past all matches. The condition arr[mid] <= target is true, so the if branch runs: left = mid + 1. This excludes mid and continues right. The search keeps going right until it lands on the first element strictly greater than target, or reaches the end.

Form 4: Rotated Search

A sorted array that has been rotated still permits O(log n) search. At any midpoint, one half is guaranteed to be perfectly sorted.

A rotation creates exactly one break in the sorted sequence, the point where the largest element wraps to the smallest. This break can only exist in one half. The other half, having no break, remains perfectly sorted.

In [4, 5, 6, 7, 0, 1, 2] with mid at index 3 (value 7), the left half [4,5,6,7] increases from 4 to 7. No break, so it is sorted. The right half [7,0,1,2] drops from 7 to 0. The break is here, so this half is not fully sorted.

At each step, determine which half is sorted, then check if the target falls within that sorted half's range. If yes, search that half. If no, the target must be in the other half.

Finding the Pivot (Minimum Element)

The minimum element in a rotated sorted array is the rotation point. Compare arr[mid] with arr[right], not arr[left]. Consider [3, 1, 2]: comparing mid (value 1) with left (value 3) gives 3 > 1, which suggests searching right, but the minimum IS mid. Comparing with right produces clean logic: if arr[mid] > arr[right], a drop must exist between mid and right, so the minimum is in the right half. If arr[mid] <= arr[right], the segment from mid to right is sorted with no drop, so the minimum is at mid or to its left.

Peak Element Problems

Binary search applies to unsorted arrays when local structure provides a monotonic direction toward the answer. A peak element is any element greater than both neighbors. (Boundaries are treated as negative infinity, so the first or last element can be a peak if larger than its single neighbor.)

If arr[mid] < arr[mid+1], a peak is guaranteed to exist on the right. Either the array keeps ascending until the end (making the last element a peak, since the boundary is negative infinity), or it eventually descends (making that turning point a peak). In both cases, moving right finds a peak.

Form 5: Binary Search on Answer

Rather than searching within an array, this form searches the space of possible answers. It solves optimization problems where the answer has a monotonic feasibility boundary.

Direct approaches to these optimization problems often require exponential time. Enumerating all possible splits or assignments grows combinatorially. The insight is to flip the question: instead of asking "what is the optimal answer?", ask "given a candidate answer X, is X achievable?" This second question typically has a simple O(n) greedy solution.

The answer space forms a monotonic boundary. For minimization problems like "minimum speed to finish," small values fail and large values succeed. The boundary between failure and success is exactly the answer. Binary search locates this boundary in O(log(range)) feasibility checks.

Recognition. The problem asks to "minimize the maximum" or "maximize the minimum" of some quantity. Another signal is when the problem has a natural feasibility check: "can we achieve X using at most k resources?"

Three Steps: Define Range, Check Feasibility, Search

1. Define the answer range. Determine the smallest and largest possible answers. The minimum is usually a constraint (the largest element must fit). The maximum is usually trivial (the entire sum).

2. Write a feasibility function. For a candidate answer X, the function returns true if X is achievable and false otherwise. This function typically uses a greedy simulation.

3. Binary search for the boundary. The answer space has a monotonic property: once a candidate works, all easier candidates also work. Find the boundary where infeasible becomes feasible (or vice versa).

Koko Eating Bananas

Given piles of bananas and h hours, find the minimum eating speed k (bananas per hour) to finish all piles within h hours.

(pile + k - 1) // k computes the ceiling of pile/k using integer arithmetic. Adding k-1 before dividing ensures any remainder rounds up. This avoids floating-point precision issues with large numbers.

The answer space [1, max(piles)] has a monotonic property: small k means cannot finish (false), large k means can finish (true). Binary search finds the boundary where false becomes true.

Minimizing the Maximum

Split an array into m subarrays to minimize the largest subarray sum. Binary search on the answer: the search space is [max(nums), sum(nums)]. The lower bound is max(nums) because each element must belong to exactly one subarray, so no subarray sum can be less than the largest element.

The feasibility function greedily assigns elements to subarrays. If the current sum exceeds the candidate, start a new subarray. If you need more than m subarrays, the candidate is too small.

Why the Runtime Works

Each comparison eliminates half the remaining candidates. After k comparisons, n/2^k candidates remain. When n/2^k = 1, the search terminates. Solving for k gives k = log₂(n).

Each doubling of the array size adds only one comparison. A billion elements require only about 30 comparisons.

For binary search on the answer, the runtime is O(log(range) * C) where C is the cost of the feasibility check. If the feasibility check is O(n), the total is O(n log(range)). For Koko eating bananas with max(piles) = 10⁹, this is about 30 feasibility checks, each scanning the array once.

Binary search on a sorted array uses O(1) space. Binary search on the answer uses O(1) space beyond the input. The space cost is always the feasibility function's requirements, not the search itself.

When This Pattern Breaks

No monotonic property. If no condition transitions from false to true across the search space, binary search cannot eliminate half the candidates. Searching for a value in an unsorted array with no local structure has no monotonic property. A comparison at mid tells you nothing about the values on either side.

Duplicates in rotated arrays. When arr[left] == arr[mid] == arr[right], the algorithm cannot determine which half is sorted. It can only shrink the search space by one element instead of half, degrading worst-case performance to O(n). This is unavoidable when duplicates exist.

Continuous answer space. When the answer is a floating-point value (such as "find the square root of 2"), the loop cannot use left < right for termination because floating-point equality is unreliable. Use right - left > epsilon or run a fixed number of iterations (100 iterations gives precision to 2^-100, far beyond what floating-point can represent).

Non-monotonic feasibility. If the feasibility function does not transition cleanly from false to true (or vice versa), binary search may converge to the wrong point. For example, if some speeds can finish and some faster speeds cannot (due to non-uniform pile sizes with a different constraint structure), the boundary is not monotonic and binary search does not apply.

Choosing the Right Form

The first question is: what is the search looking for? An exact value that may or may not exist calls for exact search with an explicit "found" return. A boundary position (first occurrence, insertion point, first satisfying some condition) calls for lower or upper bound. An optimal value with a feasibility check calls for binary search on the answer.

A common mistake is using exact search when boundary finding is needed. If the problem asks for "the first position where X holds" or "the smallest value satisfying Y," the answer may not be at any specific array element that matches target. The search narrows to a boundary, not a match.

Another mistake is confusing lower and upper bound. Both use the same loop structure, differing only in the comparison operator. Lower bound finds where arr[i] >= target first becomes true. Upper bound finds where arr[i] > target first becomes true. Using the wrong one shifts the result by one position.

Debugging the Search

Most binary search bugs come from inconsistent boundary choices. When your solution hangs, returns wrong results, or fails edge cases, check these questions in order.

Is the search space shrinking every iteration?

Fix 1: Use left = mid + 1 instead of left = mid. The +1 guarantees progress. This works when mid can be safely excluded from the search space.

Fix 2: When you need left = mid (because mid cannot be excluded), bias mid rightward: mid = (left + right + 1) // 2. With left=5, right=6, this gives mid = (5+6+1)//2 = 6 instead of 5, so left = mid actually moves left forward.

Is the search space model consistent?

Is the comparison operator correct?

Does the code handle edge cases?

Empty array: With length 0, the initial condition left < right (where right = 0) or left <= right (where right = -1) is false immediately. The loop never runs. For exact search, return -1. For boundary finding, return 0 (the insertion point at the beginning).

Single element: The loop should execute exactly once and then terminate. Trace through to verify that mid is computed correctly and that the update moves toward termination. A common bug is setting left = mid when mid = 0 and left = 0, which never advances.

All elements identical: For lower bound (using <), every comparison is false, so right = mid runs repeatedly, collapsing to 0 (the first occurrence). For upper bound (using <=), every comparison is true, so left = mid + 1 runs repeatedly, collapsing to length (past the last occurrence).

Target outside range: If target is smaller than all elements, every comparison sends the search left, and lower bound returns 0. If target is larger than all elements, every comparison sends the search right, and lower bound returns length. Always validate the returned index before accessing arr[index]. An index of length is valid for insertion point but will cause an out-of-bounds error if accessed directly.

Integer overflow in mid

Practice Problems

Binary search problems progress from basic sorted array searches to complex answer-space patterns. The skill is recognizing the monotonic property that enables binary search.

Tier 1: Foundational

Tier 2: Lower and Upper Bound

Tier 3: Rotated Array

Tier 4: Peak Element

Tier 5: Binary Search on Answer

Reference Templates

Use when the problem asks whether a specific target exists and should return immediately on equality.

Use when the problem asks for the first position where a condition becomes true.

Use when the problem asks for the first position strictly past all matching values.

Use when the array is sorted but rotated and one half is always sorted.

Use when the answer is a value and feasibility is monotonic.

Use when the rotation point is the answer, not the target value.

Use when the array is unsorted but local slope guarantees a peak direction.

Form Recap

Exact search uses inclusive bounds [left, right] with left <= right. Each iteration either finds the target and returns, or excludes mid with mid + 1 or mid - 1. The loop exits with zero candidates when left passes right, meaning the target is absent.

Lower bound finds the first position where arr[i] >= target. When arr[mid] equals target, the search continues left because an earlier match may exist. Upper bound finds the first position where arr[i] > target by changing the comparison from < to <=. Both use the half-open search space [left, right) with left < right.

Rotated search identifies which half is sorted by comparing arr[left] with arr[mid]. The target is checked against the sorted half's range. If it falls within that range, search that half. Otherwise search the other half. Duplicates can break the sorted-half detection and degrade worst-case performance to O(n).

Binary search on the answer inverts the optimization question into a feasibility question. The answer space has a monotonic boundary between infeasible and feasible candidates. A greedy feasibility check at each midpoint determines which half to eliminate. The structure is identical to lower bound search, but the search space is the range of possible answers rather than array indices.

Rebuilding the Pattern

When binary search feels unclear after time away, do not start by remembering whether to use <= or <. Start by identifying what is being searched and what condition splits the search space.

If the problem asks whether a specific value exists, the search is exact. If the problem asks for the first position satisfying a condition, the search is a boundary search. If the problem asks to minimize or maximize some quantity, the search is on the answer space. That identification determines the form, and the form determines the boundary choices.

The boundary choices must be internally consistent. Inclusive search space [left, right] pairs with left <= right, mid + 1, and mid - 1. Half-open search space [left, right) pairs with left < right, mid + 1, and right = mid. Mixing conventions produces off-by-one errors or infinite loops.

The most common source of confusion is the comparison operator in boundary search. Lower bound uses arr[mid] < target because when the value equals target, the search must continue left to find earlier matches. Upper bound uses arr[mid] <= target because when the value equals target, the search must push past all matches. The difference is one character, but it determines where the search converges.

Before submitting, trace the two-element case. With left and right adjacent, verify that mid is computed correctly and that both branches make progress. If either branch leaves both pointers unchanged, the loop does not terminate.

Check Your Understanding

Use these questions to check whether you can reason through the pattern without looking at the template.