Binary Search

Not "find a value" — find where a condition flips. Exact match, boundary finding, and binary search on the answer space.

core idea

Binary search isn’t really “find a value in an array” — it’s “find the point where a monotonic condition flips.” Every problem below turns an O(n) scan into O(log n) by discarding half the remaining search space with a single comparison. What changes between problems is what you’re searching over and what counts as a hit:

shape	loop	what you’re finding
exact match	`while (left <= right)`	one specific value’s index — return the moment you hit it
boundary	`while (left < right)`	the first/last index where a condition flips false → true
search the answer	`while (left < right)` over a value range	the smallest/largest value for which a monotonic check passes

-1

one comparison at mid decides which half is provably irrelevant

when to reach for it

The input is sorted, or you can define a monotonic predicate over it — false, false, …, false, true, true, …, true, never flipping back.
You want exactly one occurrence of a value → exact match.
You want the first or last index satisfying some condition — an insertion point, a rotated array’s pivot → boundary.
The problem says “minimum/maximum X such that …” and checking a single candidate X is cheap → binary search the answer, not the array.
A linear scan works but every comparison feels like it should discard half the remaining candidates, not just one.

universal templates

Exact match — the classic form, and the one you’ll instinctively reach for first:

public int ExactMatch(int[] nums, int target)
{
    int left = 0, right = nums.Length - 1;

    while (left <= right)                     // stop once the range is empty
    {
        int mid = left + (right - left) / 2;  // overflow-safe midpoint
        if (nums[mid] == target) return mid;  // found it — stop immediately

        if (nums[mid] < target) left = mid + 1;   // nums[mid] and everything left of it is too small
        else right = mid - 1;                     // nums[mid] and everything right of it is too big
    }
    return -1;                                // target isn't in nums
}

Boundary — never return early; narrow until exactly one candidate survives:

public int Boundary(int[] nums, int target)
{
    int left = 0, right = nums.Length;        // right is one PAST the last index — exclusive

    while (left < right)                      // stop when left == right: one candidate left
    {
        int mid = left + (right - left) / 2;
        if (Condition(nums[mid], target))
            right = mid;                      // mid satisfies it — it MIGHT be the boundary, keep it
        else
            left = mid + 1;                   // mid doesn't — the boundary is strictly after it
    }
    return left;                              // first index where Condition holds
}

Search the answer reuses the boundary skeleton verbatim — left/right just span candidate answers instead of array indices, and Condition becomes a monotonic feasibility check like CanFinish(mid). Koko Eating Bananas, below, is the template instance.

the classic infinite loop

In the boundary form, mid is left-biased — when right - left == 1, mid == left. Write left = mid on the branch that discards the low half (instead of left = mid + 1) and left never moves: infinite loop. The rule that keeps you safe: the branch that keeps mid in play uses right = mid (always fine, since mid < right); the branch that drops mid must use left = mid + 1, never left = mid.

problems

01Classic Binary SearcheasyLC #704▶ interactive
The canonical L <= R loop and the overflow-safe midpoint.
02Find First and Last PositionmediumLC #34▶ interactive
Boundary finding: on a match, keep searching the direction you care about.
03Find Minimum in Rotated Sorted ArraymediumLC #153
The L < R boundary form meets the rotated array — converge on the pivot.
04Search in Rotated Sorted ArraymediumLC #33
One half is always sorted — decide which, then decide if the target is in it.
05Koko Eating BananasmediumLC #875
Binary search on the answer: monotonic CanFinish(speed) over a bounded range.

cheat sheet — binary search

recognize it

"sorted array" + find a value/index → exact match
"first/last occurrence", "insertion point" → boundary form, while (left < right)
"minimize/maximize X such that ..." with a cheap feasibility check → binary search the answer
rotated sorted array → still binary search, just a smarter discard rule (find the sorted half first)

key tricks

overflow-safe midpoint: left + (right - left) / 2, never (left + right) / 2
boundary form: right = mid keeps mid in range, left = mid + 1 discards it — never mix them up
rotated array: compare nums[mid] to an endpoint (nums[right] or nums[left]) to find which half is actually sorted
binary search the answer: left/right span candidate answers, not array indices; a monotonic CanDo(mid) replaces the array comparison
on a match with duplicates, don't return immediately — record it and keep narrowing toward the boundary you actually want

common bugs

left = mid in the boundary form when right - left == 1 — mid floors to left, so it never advances: infinite loop
(left + right) / 2 instead of the overflow-safe form
while (left < right) when the last remaining element still needs checking (should be <=), or vice versa
ceiling division written as pile / speed instead of (pile + speed - 1) / speed in "search the answer" problems
assuming the input must be sorted — the real precondition is a monotonic predicate, which sorted order is only one example of

// Binary Search

core idea

when to reach for it

universal templates

problems

cheat sheet — binary search

// connections