Binary Search

The problem it solves

You’re given an array A and a target value. You want to find the index of target (or decide it isn’t present).

• •With an unsorted array, the safest approach is linear search: check each element until you find target or reach the end. That’s O(n).
• •With a sorted array (nondecreasing order), you can do much better by using the ordering information.

Binary search is a divide-and-conquer algorithm for searching in a sorted array. The key idea: each comparison lets you discard half of the remaining candidates.

What “sorted” means here

Assume the array is sorted in nondecreasing order:

• •For indices i < j, we have A[i] ≤ A[j].

Nondecreasing allows duplicates (e.g., [1, 2, 2, 2, 5]). Binary search still works, but you must be clear on what you want when duplicates exist (any occurrence? first? last?). We’ll cover variants later.

The mental model: shrinking an interval

Binary search maintains a search interval of indices where the target could still be.

• •low = lowest index still possible
• •high = highest index still possible

At all times, you try to preserve this loop invariant:

Invariant: If target appears in the array, then its index lies within [low, high].

Each step picks the middle index mid, compares A[mid] to target, and throws away the half that can’t contain the target.

Prerequisite note (to avoid hidden gaps)

Before you code binary search confidently, you should be comfortable with:

1. 1)Integer division / floor: computing mid using floor behavior (e.g., (low + high) // 2).
2. 2)Loop invariants: understanding and maintaining “what is always true” about [low, high] each iteration.
3. 3)Edge cases: empty arrays, single-element arrays, and duplicate values.
4. 4)(Optional but useful) Comparator-based ordering: arrays sorted descending or by a custom key require adjusting comparisons.

These aren’t “extra topics”—they are exactly where most binary search bugs come from.

Why it’s O(log n)

Each iteration cuts the interval size roughly in half.

If the array length is n:

• •after 1 step: ~n/2 candidates remain
• •after 2 steps: ~n/4
• •after k steps: ~n/2ᵏ

We stop when the interval becomes empty or we find the target. The smallest k such that n/2ᵏ ≤ 1 is k ≥ log₂(n). So the number of iterations is O(log n).

Why the interval matters

Binary search isn’t just “check middle and move left/right.” It’s a careful promise about what indices are still possible.

If you lose that promise (the invariant), you can:

• •skip over the target
• •loop forever
• •read out of bounds

So we’ll be explicit about the invariant and how each update preserves it.

The standard exact-match version (closed interval)

We’ll use a closed interval [low, high] inclusive. Initialize:

• •low = 0
• •high = n - 1

Loop while the interval is non-empty:

• •condition: low <= high

Compute middle:

• •mid = low + (high - low) // 2

(The low + (high - low) form avoids overflow in languages with fixed-size integers; in Python it’s not necessary, but it’s a good habit.)

Compare:

• •If A[mid] == target: return mid
• •If A[mid] < target: discard left half including mid → set low = mid + 1
• •If A[mid] > target: discard right half including mid → set high = mid - 1

If the loop ends, return “not found” (often -1).

Showing the invariant preservation

Let’s spell out what each case means.

Assume the array is sorted nondecreasing.

Case 1: A[mid] < target

Because the array is sorted, for every i ≤ mid, we have A[i] ≤ A[mid] < target.

So no index ≤ mid can hold target.

Therefore, if target exists, it must be in indices mid + 1 ... high. Setting low = mid + 1 preserves:

If target exists, it’s still in [low, high].

Case 2: A[mid] > target

Similarly, for every i ≥ mid, we have A[i] ≥ A[mid] > target.

So no index ≥ mid can hold target.

Therefore, if target exists, it must be in indices low ... mid - 1. Setting high = mid - 1 preserves the invariant.

Case 3: A[mid] == target

We’re done.

Termination: why it must end

Each iteration strictly shrinks the interval:

• •low increases (to mid + 1) or
• •high decreases (to mid - 1) or
• •we return

Since low and high are integers and the interval length can’t shrink forever without becoming empty, the loop terminates.

Concrete pseudocode

binary_search(A, target):
    low = 0
    high = len(A) - 1

    while low <= high:
        mid = low + (high - low) // 2

        if A[mid] == target:
            return mid
        else if A[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

Breathing room: trace one run

Suppose A = [2, 5, 7, 12, 19, 23, 31], target = 19.

• •Start: low=0, high=6
• •mid=3 → A[3]=12 < 19 → low=4
• •Now low=4, high=6
• •mid=5 → A[5]=23 > 19 → high=4
• •Now low=4, high=4
• •mid=4 → A[4]=19 == 19 → found at 4

Notice how [low, high] always contained index 4 until we found it.

Binary search is famous for off-by-one errors. Most bugs come from mixing interval conventions or mishandling duplicates.

1) Computing mid safely and correctly

The classic formula is:

• •mid = (low + high) // 2

In many languages, low + high can overflow if indices are large. A safer version is:

• •mid = low + (high - low) // 2

Both choose the “lower middle” when there are two middles.

2) Closed vs half-open intervals

There are two common interval conventions:

For beginners, closed intervals are often easier to reason about for exact-match search.

The most important rule is: pick one convention and stay consistent.

3) Duplicates: “any occurrence” vs “first/last occurrence”

If duplicates exist, the exact-match binary search above can return any index where A[mid] == target.

Sometimes you need a stable boundary, like:

• •lower bound: first index i where A[i] ≥ target
• •upper bound: first index i where A[i] > target

These are incredibly useful in practice (counting occurrences, insertion positions, range queries).

Lower bound (first position with A[i] ≥ target)

A common pattern uses a half-open interval [low, high):

• •Initialize: low = 0, high = n
• •While low < high:
• •mid = low + (high - low) // 2
• •If A[mid] < target, discard left including mid → low = mid + 1
• •Else, keep mid (could be answer) → high = mid

At the end, low is the smallest index with A[low] ≥ target (or n if none).

Why does high = mid (not mid - 1)? Because in half-open intervals, high is exclusive, and we want to keep mid as a candidate.

Upper bound (first position with A[i] > target)

Same structure, just change the comparison:

• •If A[mid] <= target, move low = mid + 1
• •Else, high = mid

Then the count of occurrences of target is:

4) Empty arrays and single-element arrays

Binary search should handle these without special-casing if your loop condition is correct.

• •Empty: n = 0 → high = -1 → low <= high is false immediately → return -1.
• •Single element: low=0, high=0 → one iteration checks that element.

5) Custom orderings (optional but important)

If the array is sorted descending, the direction flips:

• •If A[mid] < target, you must go left (because values decrease to the right).

If the array is sorted by a key (e.g., objects sorted by age), compare using that key consistently.

A useful way to stay sane is to think: you need a monotonic predicate (something that switches from false to true once). Lower/upper bound are built exactly on that principle.

1) Fast lookup in sorted data

Binary search is the core primitive behind many “fast membership” tasks when data is stored sorted:

• •searching in a sorted array
• •searching in a sorted list of timestamps
• •dictionary-like behavior when updates are rare but queries are frequent

Time complexity is O(log n) per query, with O(1) extra space.

2) Insertion position and maintaining sorted order

Using lower bound, you can find where to insert an element while maintaining sorted order.

• •Find index i = lower_bound(A, x)
• •Insert at i (in an array, insertion itself is O(n) due to shifting, but the search for position is O(log n))

This is common in:

• •building sorted lists incrementally
• •coordinate compression (collect values, sort, then binary search indices)

3) Range counting and frequency queries

If the array is sorted, you can count how many elements equal target or lie in a range [L, R].

• •occurrences of x: ub(x) - lb(x)
• •count in [L, R]: lb(R+ε) - lb(L) (conceptually), or more directly ub(R) - lb(L)

4) Binary search on the answer (a bigger idea)

A powerful pattern is binary searching over a value space when you have a monotonic condition.

Example shape:

• •You want the smallest value k such that feasible(k) is true.
• •If feasible(k) is true, then feasible(k+1) is also true (monotonic).

Then you can binary search k even if there is no array.

This is used for:

• •minimum capacity / maximum speed problems
• •scheduling and allocation
• •optimization with monotonic constraints

This lesson node focuses on array search, but learning lower/upper bound sets you up for that broader technique.