Skip to content
Velloreth
Programming 7 min read

Binary Search Explained: Halving Your Way to O(log n)

Binary search finds a value in a sorted array by halving the search space each step. Learn the algorithm, the off-by-one traps, and real variants.

By

The idea in one paragraph

Binary search finds a value in a sorted collection by looking at the middle element and discarding the half that cannot contain the target. Repeat until you find it or the space is empty. Because each step halves what remains, a million elements take about twenty comparisons instead of a million.

That is the entire algorithm. Everything else is implementation detail and edge cases.

The iterative implementation

function binarySearch(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) low = mid + 1;
    else high = mid - 1;
  }

  return -1;
}

Four things to notice, because each is a place people get it wrong.

low <= high, not low < high. With low < high you exit the loop when the range has one element left, and you never check that element. A single-element array would always return -1.

mid + 1 and mid - 1, not mid. The midpoint has already been checked and ruled out. Keeping it in the range means the range may not shrink, and the loop can run forever.

low + (high - low) / 2. The obvious (low + high) / 2 overflows in fixed-width integer languages when both values are large. Java’s Arrays.binarySearch had exactly this bug for nine years before it was fixed in 2006. JavaScript numbers are doubles so it does not bite there, but the habit is worth forming.

Math.floor. In languages with integer division this is automatic. In JavaScript, division produces a float, and sorted[2.5] is undefined.

Why it is O(log n)

Each iteration halves the search space. Starting with n elements:

StepElements remaining
01,000,000
1500,000
2250,000
531,250
10977
201

After k steps, n / 2ᵏ elements remain. The loop ends when that reaches 1, so k = log₂(n). For a million elements, that is about 20.

This is why binary search is the standard answer to “how do you find something in a huge sorted dataset”. A linear scan of a billion records takes a billion comparisons; binary search takes thirty.

The sorted requirement

Binary search assumes the data is sorted. If it is not, the algorithm does not fail loudly — it returns a wrong answer, usually -1, and you spend an afternoon debugging.

binarySearch([3, 1, 4, 1, 5], 4); // -1, even though 4 is present

The comparison sorted[mid] < target is meaningless on unsorted data, so the algorithm discards the half that actually contains the target.

This is why binary search is almost always paired with a sort. Sorting is O(n log n), so if you search once, a linear scan is cheaper. If you search many times, sorting once and binary searching each time wins.

The generalised pattern

Exact lookup is the textbook case, but the real power of binary search is that it answers any question of the form “find the boundary where a condition flips from false to true”.

Lower bound: first index where value >= target

function lowerBound(sorted, target) {
  let low = 0;
  let high = sorted.length;
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (sorted[mid] < target) low = mid + 1;
    else high = mid;
  }
  return low;
}

This returns the insertion point — where the target would go to keep the array sorted. It is what Array.prototype.findIndex cannot do efficiently, and it is the basis of bisect in Python and lower_bound in C++.

Upper bound: first index where value > target

Change the comparison to <= and you get the other boundary. Together, the two bounds give you the count of occurrences of a value in O(log n).

Binary search on the answer

The most powerful form: when a problem asks for the smallest value satisfying some monotonic condition, binary search the answer space directly.

// Smallest capacity that ships all packages within `days`
function shipWithinDays(weights, days) {
  let low = Math.max(...weights);
  let high = weights.reduce((a, b) => a + b, 0);
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (canShip(weights, days, mid)) high = mid;
    else low = mid + 1;
  }
  return low;
}

You never search an array here. You search the range of possible answers, using a predicate that is monotonic — if capacity c works, every capacity above c works. That monotonicity is the only requirement.

This technique solves a surprising range of problems: minimum time to complete tasks, smallest divisor, kth smallest element in a matrix, and many optimisation problems that look like they need dynamic programming.

Recursive form

function binarySearchRecursive(sorted, target, low = 0, high = sorted.length - 1) {
  if (low > high) return -1;
  const mid = low + Math.floor((high - low) / 2);
  if (sorted[mid] === target) return mid;
  if (sorted[mid] < target) return binarySearchRecursive(sorted, target, mid + 1, high);
  return binarySearchRecursive(sorted, target, low, mid - 1);
}

The recursive form is clearer to read but uses O(log n) stack space and is slower in practice due to call overhead. Prefer the iterative version in production.

Common bugs and how to avoid them

Infinite loop. Caused by not shrinking the range. If you write low = mid instead of low = mid + 1, and the range has two elements, mid equals low and the range never shrinks.

Missing the last element. Caused by low < high when you need low <= high. The fix is to decide deliberately whether your range is inclusive or half-open, and be consistent.

Overflow. (low + high) / 2 overflows in Java, C, and Go for large arrays. Use low + (high - low) / 2.

Wrong boundary variant. Lower bound and upper bound differ by one comparison. Mixing them up gives an off-by-one result that is easy to miss in testing.

Searching unsorted data. No error, just wrong answers. Assert sortedness in tests.

Unsorted data you search once. Sorting costs O(n log n), which is worse than a single O(n) scan.

Linked lists. Reaching the middle costs O(n), so the total is O(n log n) at best — worse than a linear scan.

Small arrays. For fewer than about 20 elements, a linear scan is faster because it has no branch misprediction and no setup cost. Many standard libraries switch to linear search below a threshold.

Data that changes constantly. Every insertion into a sorted array costs O(n) to shift elements. If you insert and search in equal measure, a balanced tree or a hash map is better.

Where it shows up in practice

  • Database indexes — B-trees are binary search generalised to many-way branching, which is why indexed lookups are fast.
  • git bisect — binary searches your commit history to find the commit that introduced a bug.
  • Version control and package managers — resolving version ranges uses binary search over sorted version lists.
  • Autocomplete and typeahead — finding the range of completions for a prefix.
  • Numerical methods — root finding by bisection is binary search on a continuous function.
  • Rate limiting and capacity planning — binary searching for the smallest configuration that meets a target.

For the complexity reasoning behind these costs, see Big-O notation explained. For the structures that make sorted search possible, data structures every developer should know and trees and graphs explained. If you are practising for interviews, debugging strategies that work covers the reasoning that matters.

Quotable summary

Binary search finds a value in a sorted collection by comparing with the middle element and discarding the half that cannot contain the target, halving the search space each step for O(log n) time and O(1) space. It requires sorted input and returns wrong answers silently on unsorted data. The generalised form answers any monotonic yes/no question, which makes it applicable to boundary finding, insertion points, and optimisation problems where the answer space is searched rather than an array. The most common bugs are off-by-one errors in the loop condition and midpoint update, and integer overflow in the midpoint calculation.

Frequently asked questions

What is binary search in simple terms?
Binary search finds a value in a sorted list by checking the middle element, then discarding the half that cannot contain the value, and repeating. Each step halves what is left, so a million items take about twenty checks.
Why does binary search require a sorted array?
Because the algorithm decides which half to discard by comparing the target with the middle element. That decision is only valid if the data is ordered. On unsorted data binary search returns wrong results without any error.
What is the time complexity of binary search?
O(log n) time and O(1) space for the iterative version. The recursive version uses O(log n) space for the call stack. Each comparison halves the remaining search space.
What is the most common binary search bug?
Off-by-one errors. Using low < high instead of low <= high, or updating low = mid instead of low = mid + 1, causes either an infinite loop or a missed element. The midpoint must always be excluded from the half you keep.
Why write mid = low + (high - low) / 2?
Because low + high can overflow a fixed-width integer when both are large, producing a negative midpoint and an out-of-bounds access. Computing the difference first keeps the intermediate value small. It is a real bug that shipped in Java's standard library for years.
Can binary search be used on a linked list?
Not usefully. Binary search needs O(1) access to the middle element, but reaching the middle of a linked list costs O(n), which removes the logarithmic benefit. Use a sorted array or a balanced tree instead.