juniorSearching

How does binary search work and when can you use it?

Updated Feb 20, 2026

Short answer

Binary search repeatedly halves a sorted range: compare the target to the middle element, discard the half that cannot contain it, and repeat. That gives O(log n) — a million elements take about twenty comparisons. The precondition is absolute: the data must already be sorted, and if it is not, the algorithm silently returns wrong answers rather than failing.

Deep explanation

Python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:                     # <= : a one-element range is still valid
        mid = lo + (hi - lo) // 2       # avoids overflow in fixed-width languages
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1                # +1 / -1 guarantee progress
        else:
            hi = mid - 1
    return -1

Three details cause nearly every bug:

  • `lo <= hi`, not `<`. With <, a range that has narrowed to one element is never examined, so the search misses targets sitting at the boundary.
  • `mid + 1` and `mid - 1`. Assigning lo = mid leaves the range unchanged when lo and hi are adjacent, and the loop spins forever.
  • `lo + (hi - lo) // 2`. In C or Java, (lo + hi) / 2 can overflow a 32-bit int on large arrays — a bug that sat in the JDK's own binary search for nine years.

When it applies. The requirement is really monotonicity, not sortedness as such — the answer space must be splittable into a "no" region followed by a "yes" region. That generalisation is what lets binary search solve problems with no array in sight: finding the first version that fails a test, the minimum capacity that completes a job in time, or the square root of a number to a given precision.

When it does not. Unsorted data — sorting first costs O(n log n), so for a single lookup a linear scan is cheaper. Linked lists, where reaching the middle is itself O(n), which erases the benefit. And very small arrays, where a linear scan's cache-friendly access usually wins on wall-clock despite the worse complexity.

Real-world example

Finding the first commit that introduced a bug, over 10,000 commits:

Python
def first_bad(commits, is_bad):
    lo, hi = 0, len(commits) - 1
    answer = -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if is_bad(commits[mid]):
            answer = mid        # candidate; look for an earlier one
            hi = mid - 1
        else:
            lo = mid + 1
    return answer

Roughly 14 builds rather than 10,000. The monotonic property that makes it valid: once a commit is bad, every later commit is bad. This is exactly what git bisect does.

Common mistakes

  • - Running it on unsorted data, which returns a plausible wrong answer instead of an error.
  • - Writing `while lo < hi`, so a single-element range is never checked and boundary targets are missed.
  • - Assigning `lo = mid` or `hi = mid` without the offset, producing an infinite loop when the range is two elements wide.
  • - Computing `(lo + hi) / 2` in a fixed-width language and overflowing on a large array.
  • - Returning the first match found when the task calls for the first or last occurrence among duplicates — that needs the search to continue in one direction rather than stop.

Follow-up questions

  • How do you find the first occurrence of a duplicated value?
  • Why can't binary search be used efficiently on a linked list?
  • What does it mean to binary search over the answer space?
  • When is a linear scan actually faster?

More Searching interview questions

View all →