Binary Search

1Halve a sorted search space

On a sorted array, binary search compares the middle element to the target and discards half the remaining range each step. That is why the time is O(\log n): after about \lceil \log_2 n \rceil comparisons the range collapses to one cell. The recurrence is T(n) = T(n/2) + O(1).

Figure. First mid lands on 5; target 7 is larger, so the left half is discarded.

One comparison

1. Pick midIn the current [low, high] range, read the middle index.
2. CompareEqual ⇒ found. Target larger ⇒ search the right half. Target smaller ⇒ search the left half.
3. ShrinkUpdate low or high so the discarded half never appears again.

Classic binary search

def binary_search(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Coding lab. Find 7 in the six-number row runs in the app, with checks on your output.

2Overflow-safe midpoint

The naive mid = (low + high) / 2 can overflow when low and high are large signed integers. Writing mid = low + (high − low) / 2 computes the same index using a difference that fits when the indices themselves fit. Same answer, fewer surprise bugs — a classic interview footgun.

Figure. mid = low + (high − low) / 2 is the same index as (low + high) / 2, but the sum low+high can pass the representable maximum while the half-difference stays between the endpoints.

Why the rewrite is safer

1. Same mathlow + (high − low)/2 equals (low + high)/2 for real numbers.
2. Smaller sumhigh − low is at most the array length in index space; low + that half stays inside representable bounds more often.
3. HabitUse the safe form every time — it costs nothing when overflow is impossible and saves you when it is not.

3Bounds and loop conditions

Off-by-one bugs live in the loop condition and the mid update. Inclusive bounds with while low ≤ high pair with high = mid − 1 and low = mid + 1. Half-open [low, high) often uses while low < high and high = mid. Mixing the two conventions is how infinite loops and skipped cells appear. Pick one style and keep every update consistent with it.

Keep the Bounds and loop conditions table paired: inclusive low ≤ high with mid±1 updates, or half-open low < high with high = mid — never mix the two conventions.

Inclusive style checklist

1. Rangelow and high are both valid indices (or high starts at n−1).
2. Loopwhile low ≤ high — empty range is low > high.
3. Discard midOn move right, low = mid + 1. On move left, high = mid − 1. Never leave mid in the range after rejecting it.

4Lower and upper bound

When duplicates exist, classic equality search returns any hit. Lower bound finds the first index whose value is ≥ target; upper bound finds the first index whose value is > target. Together they give the half-open range of equal values, still in O(\log n) — insertion points and frequency counts fall out of the same pair.

Figure. Lower bound of 2 is index 1; upper bound is index 4 (first > 2). The equal run is the bracketed triple.

Lower bound (first ≥ target)

1. CandidateKeep an answer index, initially n ("not found / insert at end").
2. Mid ≥ targetRecord mid as a candidate and search left (high = mid − 1).
3. Mid < targetSearch right (low = mid + 1).

5Binary search on the answer

Sometimes the array is not what you search — the answer value is. If a feasibility predicate is monotonic (once speed s works, every larger speed also works), binary-search the answer between a low and high bound and keep the extreme feasible value. Cost is O(\log(\text{range}) \times cost of one feasibility check). "Minimum capacity / speed / days that works" is the signature.

Figure. Binary search on the answer walks a numeric range where a predicate flips from false to true once — return the first true.

Minimize a feasible value

1. Boundslow = smallest conceivable answer; high = largest (often a max input).
2. Check midIf feasible(mid), record mid and search left for something smaller.
3. InfeasibleSearch right — mid was too aggressive.

6Sorted or monotonic first

Plain binary search on indices assumes the array is sorted in the direction your comparisons expect. If it is not, either sort first (O(n \log n) — often slower than a linear scan for one query) or use a different structure. Search-on-answer replaces "sorted array" with "monotonic predicate," but something still has to be monotonic. Applying the halving loop to unsorted data is undefined behavior for correctness, not merely slow.

Figure. Binary search needs a sorted (or monotonic) space; an unsorted row makes every midpoint guess meaningless.

Before you binary-search

1. Name the orderIs the array sorted, or is the predicate on the answer monotonic?
2. If neitherDo not halve. Scan, hash, or sort deliberately and own the cost.
3. If you sort for one queryCompare O(n \log n) sort-plus-search against O(n) linear — sorting rarely wins for a single lookup.

7Iterative versus recursive space

The iterative loop uses O(1) extra space. A recursive formulation that binary-searches a half in a call uses O(\log n) stack space for the depth of the recursion. Same comparisons, different memory profile — prefer iterative unless the recursive shape makes the invariant clearer for a variant you are proving.

Figure. Same O(\log n) comparisons; recursion pays O(\log n) call-stack frames the iterative loop does not.

Space accounting

1. IterativeTwo or three index variables on the stack frame of one function — constant space.
2. RecursiveEach call waits on a half; depth is the number of halvings ≈ log n.
3. Time unchangedBoth are O(\log n) comparisons on a sorted array.

8Complexity and the recurrence

Binary search's time recurrence T(n) = T(n/2) + O(1) unfolds to O(\log n) because you pay constant work per level and there are \Theta(\log n) levels until n shrinks to 1. Search-on-answer replaces n with the width of the answer range: O(\log(\text{range}) \times C) when each feasibility check costs C. Memorize the shape; derive the log from the recurrence rather than treating it as a slogan.

Count the halvings on the Halve a sorted search space strip: each step cuts the live range in two, so n shrinks to 1 in \lfloor \log_2 n \rfloor probes.

Unrolling T(n)

1. One stepPay O(1), leave a subproblem of size n/2.
2. k stepsSize is n/2^k. Stop when that size is 1 ⇒ k ≈ log₂ n.
3. Totalk constant-time steps ⇒ O(\log n).