Free lesson · DSA Mastery - Interview Prep, End to End

Introduction to Binary Search

Medium6 min readdsabinary-search

Introduction to Binary Search

Binary search is the most important single-direction divide-and-conquer technique: repeatedly halve a search space to locate a target or a boundary in O(log n). Where general divide and conquer splits into pieces and combines their results, binary search discards one half every step - you never need to look at the eliminated portion again. That one idea, applied to a sorted array, finds any element in about 20 comparisons out of a million. But the real power of binary search is far broader than sorted-array lookup: it works on any monotonic predicate, which lets it search rotated arrays, two-dimensional matrices, and even abstract "answer spaces" where the array is conceptual rather than physical. This section builds from the classic template up to those advanced applications, and this opening topic establishes the mental model and the implementation discipline that prevents the bugs binary search is notorious for.

The insight: binary search doesn't really require a sorted array - it requires a monotonic condition. If you can define a yes/no test that is false, false, …, false, then true, true, …, true across the search space (or the reverse), binary search can find the boundary between the two regions in O(log n). The sorted array is just the most familiar case where "is this element ≥ target?" happens to be monotonic.

The Core Pattern

The classic binary search maintains a search interval [lo, hi] and repeatedly examines the midpoint:

int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   // avoid overflow; midpoint of [lo, hi]
        if (a[mid] == target) return mid;
        else if (a[mid] < target) lo = mid + 1;   // target is in the right half
        else hi = mid - 1;                          // target is in the left half
    }
    return -1;   // not found
}

Three details make or break a binary search, and most bugs come from getting them wrong:

• The loop condition - lo <= hi versus lo < hi changes when the loop stops and what invariant holds at the end.
• The midpoint formula - lo + (hi - lo) / 2 avoids the integer overflow that (lo + hi) / 2 can cause for large indices.
• The update step - mid + 1 / mid - 1 versus mid determines whether the interval always shrinks (it must, or you loop forever).

Why O(log n)?

Each iteration discards half the remaining search space. Starting from n candidates, after one step there are n/2, then n/4, and so on. The loop ends when one candidate remains, which happens after about log2(n) halvings. For a million elements that's roughly 20 steps; for a billion, about 30. This logarithmic shrinkage is why binary search is one of the fastest things in computing.

graph TD
    A["search space: n candidates"] --> B["examine midpoint"]
    B --> C{"target vs midpoint"}
    C -->|equal| D["found"]
    C -->|"target larger"| E["discard left half → n/2 remain"]
    C -->|"target smaller"| F["discard right half → n/2 remain"]
    E --> B
    F --> B

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This diagram shows binary search halving the space. We examine the midpoint, compare it to the target, and discard the half that cannot contain the target. Each step halves the remaining candidates, giving logarithmic time.

The Two Templates: Find Exact vs Find Boundary

There are two binary search styles, and knowing which you need is half the battle.

The exact-match template (above) uses lo <= hi and returns as soon as it finds the target. Use it when you want the element equal to a value.

The boundary template finds the first position satisfying a condition - the leftmost true in a false-false-true-true sequence. It uses lo < hi, never excludes the midpoint on the "true" side, and converges lo and hi onto the boundary:

int firstTrue(int lo, int hi) {       // find smallest index where predicate is true
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (predicate(mid)) hi = mid;       // mid might be the answer; keep it
        else lo = mid + 1;                  // mid is not; discard it
    }
    return lo;   // lo == hi: the boundary
}

Important: Most "hard" binary search problems are really boundary searches in disguise. The question is rarely "is this value present?" but "what is the smallest/largest value for which some condition holds?" Mastering the boundary template unlocks the rotated-array, answer-space, and matrix problems later in this section.

Binary Search on a Monotonic Predicate

The deepest idea in this section: binary search applies whenever there's a monotonic predicate over the search space. Picture a function f(x) that returns false for all x below some threshold and true for all x at or above it. Binary search finds that threshold without ever evaluating f more than O(log n) times.

This reframing is powerful because the "search space" need not be an array at all. In Koko Eating Bananas (later in this section), you binary-search over eating speeds; in Split Array Largest Sum, over possible maximum sums. The array is conceptual - the candidate answers, ordered - and the predicate is "can we achieve the goal with this candidate?" If that predicate is monotonic (achievable at some value implies achievable at all larger/smaller values), binary search finds the optimal answer.

graph LR
    A["x small: predicate FALSE"] --> B["... FALSE"]
    B --> C["threshold"]
    C --> D["TRUE ..."]
    D --> E["x large: predicate TRUE"]

    style A fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style B fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9

This diagram shows a monotonic predicate: false for small values, then true for all values past a threshold. Binary search locates the threshold between the false region and the true region in logarithmic time.

When To Reach For Binary Search

Recognize a binary search problem by these signals:

• The data is sorted, or can be sorted, or has a monotonic structure (even a rotated one).
• The problem asks for a target, a boundary (first/last position, insert point), or an optimal value under a monotonic feasibility test.
• The phrasing mentions "minimum/maximum value such that …" - a strong hint for binary-search-on-answer.
• A brute-force scan would be O(n) or O(n²) and the constraints (n up to 10^5 or more, values up to 10^9) demand something faster.

If the data isn't sorted and has no monotonic structure, binary search usually doesn't apply directly - but ask whether sorting first, or searching over an answer space, restores monotonicity.

Variations & Follow-ups

Why is lo + (hi - lo) / 2 preferred over (lo + hi) / 2?

For large indices, lo + hi can exceed the maximum int and overflow to a negative number, producing a wrong (or out-of-bounds) midpoint. Computing lo + (hi - lo) / 2 keeps the intermediate value within range - it's mathematically identical but overflow-safe. This is a classic, real-world bug (it was present in the JDK's own binary search for years).

When do I use lo <= hi versus lo < hi?

Use lo <= hi for exact-match search where the interval can shrink to a single element you still need to test, and where you exit by exhausting the interval. Use lo < hi for boundary search, where lo and hi converge onto the answer and the loop ends with lo == hi pointing at it. Mixing them up causes off-by-one bugs or infinite loops.

How do I guarantee the loop terminates?

The interval must strictly shrink every iteration. In the exact template, mid + 1 and mid - 1 always exclude mid, so it shrinks. In the boundary template, hi = mid keeps mid but lo = mid + 1 excludes it - and you must compute mid as the lower midpoint (lo + (hi - lo) / 2) so that hi = mid makes progress. Getting this wrong is the cause of binary search infinite loops.

Is binary search always O(log n)?

The number of iterations is O(log n), but the total time also depends on the cost of each comparison or predicate evaluation. For a plain array lookup each step is O(1), so it's O(log n). For binary-search-on-answer, each predicate check might be O(n) (a feasibility scan), giving O(n log n) overall - still far better than the O(n²) or exponential brute force it replaces.

Why This Topic Matters

Binary search is one of the highest-leverage patterns in all of interview preparation: it appears constantly, it's easy to get subtly wrong, and its generalization to monotonic predicates unlocks an entire class of optimization problems that look nothing like array lookup. Internalizing the two templates (exact and boundary), the overflow-safe midpoint, and the monotonic-predicate reframing now means every problem in this section is a variation on a foundation you already understand.

The next topic, Binary Search, implements the canonical exact-match search on a sorted array - the literal version of the template above. It's the simplest possible application, but writing it with correct loop bounds, an overflow-safe midpoint, and a clean not-found return is the essential muscle memory that every later problem builds on.

Back to DSA Mastery - Interview Prep, End to End