Binary Search Fundamentals

Binary search is much more than “search in a sorted array”. It is a general technique for finding a boundary where a condition switches from false to true.

Once you learn to view problems as “find the smallest x such that condition(x) is true”, a large class of interview questions become straightforward.

Classic: Search in a Sorted Array

Given a sorted array a and a target x, the basic question is: does x exist, and if so, what is an index where a[i] == x?

One robust template is:

Java
int lo = 0, hi = n - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == x) {
        return mid;
    } else if (a[mid] < x) {
        lo = mid + 1;
    } else {
        hi = mid - 1;
    }
}
return -1; // not found

Key points:

Always compute mid as lo + (hi - lo) / 2 to avoid overflow.
Loop condition lo <= hi matches the invariant “search space is [lo, hi] inclusive”.

Thinking in Terms of Boundaries

More generally, we often want:

Find the smallest index i such that condition(i) is true,
given that condition(i) is false for all i < answer and true for all i >= answer.

This is a monotonic predicate. We can binary search on the range [lo, hi]:

Java
int lo = 0, hi = n; // hi is exclusive
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (condition(mid)) {
        hi = mid; // answer is in [lo, mid]
    } else {
        lo = mid + 1; // answer is in [mid+1, hi]
    }
}
// lo == hi is the first index where condition(i) is true (or n if none)

This “first true” / “lower bound” pattern is more universal than the simple array search.

Binary Search on Answer Space

Sometimes the array is not explicitly given. Instead:

You can check if an answer X is feasible (condition(X)).
As X increases, feasibility flips from false to true (or vice versa).

Typical examples:

Minimum capacity of a ship to ship packages within D days.
Minimum eating speed to finish bananas in H hours.
Minimum radius so every house is covered by a heater.

General approach:

Identify the answer range [lo, hi].
Define a monotonic predicate can(X):
- true if we can satisfy the problem with parameter X.
Use binary search to find the smallest X such that can(X) == true.

This is often more stable and simpler than trying to directly compute X with math.

Common Pitfalls and How to Avoid Them

Off‑by‑One Errors

Make the invariant explicit:
- Are you searching on [lo, hi] inclusive, or [lo, hi) half‑open?
Ensure that after updating lo or hi, the invariant still holds.

Tip: pick one template (inclusive or half‑open) and stick to it in all problems.

Infinite Loops

In each branch, ensure the search interval shrinks:
- For inclusive: hi = mid - 1 or lo = mid + 1.
- For half‑open: hi = mid or lo = mid + 1.
Never write lo = mid and hi = mid in the same template.

Wrong Predicate

When doing “binary search on answer space”, the most subtle bugs come from:

can(X) is not actually monotonic.
You misclassified the boundary (e.g. should be “first feasible” but you search for last).

Always test can(X) on:

Lower edge (lo).
Upper edge (hi).
A few points around the expected answer.

When to Reach for Binary Search

Use this checklist:

Is there some variable X (index, capacity, time, radius, …) such that:
- For all X < answer, the condition is false.
- For all X >= answer, the condition is true (or the reverse)?
Can you implement condition(X) in O(f(X)) time that is cheap enough?
Is the answer in a known numeric or index range?

If so, binary search with a monotonic predicate is often the cleanest solution.

Practice Recommendations

To truly master binary search:

Implement both array search and first‑true templates without thinking.
Solve several “search on answer space” problems (ship packages, eating bananas, heaters).
For each problem, explicitly write:
- What is the answer space?
- What is can(X) and why is it monotonic?

Once you’re comfortable, many “hard” problems will suddenly feel like simple variations of the same idea.