Binary Search Visualized

Binary search is one of the most important examples of algorithmic thinking. It does not win by doing less work per step. It wins by discarding half of the remaining search space every time it makes a comparison.

That idea shows up everywhere: searching sorted arrays, locating insertion points, answering range queries, tuning thresholds, and solving monotonic decision problems. Once you understand the invariant behind binary search, you stop treating it as an interview trick and start using it as a reliable design pattern.

Why Binary Search Matters

For small inputs, linear scanning is often fine. But as data grows, checking values one by one becomes expensive. Binary search changes the growth curve by turning a problem that needs up to $n$ checks into one that needs about $\log_2 n$ checks.

That is a massive difference in practice:

Preconditions

Binary search is powerful, but it depends on strict assumptions:

• The data must be sorted according to the same rule used by comparisons
• The search space must support random access so the midpoint can be read efficiently
• The comparison must be monotonic: once the answer is on one side, it stays on that side

The Core Invariant

The most important idea in binary search is the invariant:

If the target exists, it must remain inside the current interval [left, right].

Every iteration does three things:

1. Choose the midpoint
2. Compare the midpoint value with the target
3. Discard the half that can no longer contain the answer

The algorithm is correct only if that invariant stays true after every update.

If the midpoint value is too large, everything to the right is also too large, so we move right = mid - 1.

If the midpoint value is too small, everything to the left is also too small, so we move left = mid + 1.

If the midpoint value matches the target, we are done.

Why It Is Fast

Instead of shrinking the interval by one element, binary search cuts the remaining candidates roughly in half.

After one comparison, at most $n / 2$ elements remain.

After two comparisons, at most $n / 4$ elements remain.

After $k$ comparisons, at most $n / 2^k$ elements remain.

We stop when the interval becomes size 1 or 0, so:

That gives:

This is why binary search runs in logarithmic time.

Walkthrough Example

Suppose we search for 42 in this sorted array:

[4, 9, 15, 21, 28, 34, 42, 57, 63, 71, 88]

Step 1

• left = 0
• right = 10
• mid = 5
• value at index 5 is 34

Since 42 > 34, the target cannot be in indices 0..5, so we keep only the right half.

Step 2

• left = 6
• right = 10
• mid = 8
• value at index 8 is 63

Since 42 < 63, the target cannot be in indices 8..10, so we keep only the left half of the remaining interval.

Step 3

• left = 6
• right = 7
• mid = 6
• value at index 6 is 42

Match found.

The search finished in 3 comparisons instead of scanning up to 11 values.

The Midpoint Formula

A common implementation writes:

mid = (left + right) / 2

That works mathematically, but in some languages it can overflow when left and right are both large integers.

The safer form is:

mid = left + (right - left) / 2

It produces the same midpoint while avoiding the overflow risk.

Exact Match vs Insertion Point

There are two major families of binary search:

• Exact match search: return the index only if the target exists
• Boundary search: return the first valid position, often called lower_bound or upper_bound

Boundary search is what makes binary search broadly useful in real systems. It can answer questions like:

• Where should a new value be inserted?
• What is the first value greater than or equal to x?
• What is the first timestamp after a given moment?
• What is the smallest feasible answer in a monotonic search space?

The visualizer below focuses on exact match first, because that is the easiest way to understand the interval invariant.

Code Examples

Iterative Binary Search

#include <vector>

int binarySearch(const std::vector<int>& values, int target) {
  int left = 0;
  int right = static_cast<int>(values.size()) - 1;

  while (left <= right) {
    int mid = left + (right - left) / 2;

    if (values[mid] == target) {
      return mid;
    }

    if (values[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

Lower Bound Variant

If you need the first position where a value can be inserted without breaking order, use a boundary search:

int lowerBound(const std::vector<int>& values, int target) {
  int left = 0;
  int right = static_cast<int>(values.size());

  while (left < right) {
    int mid = left + (right - left) / 2;

    if (values[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left;
}

Common Pitfalls

When binary search fails, it is usually not because the idea is hard. It is because the implementation quietly changed the interval semantics.

When To Use Binary Search

Binary search is a strong fit when:

• You have sorted data and need repeated queries
• You need a threshold, boundary, or insertion point
• You are solving a monotonic yes/no problem, not just a direct lookup

It is a poor fit when:

• The data is unsorted and sorting would cost more than a direct scan
• You do not have efficient random access
• The predicate is not monotonic

Summary

Binary search works because it preserves one invariant: if the answer exists, it must stay inside the active interval. Every comparison removes half of the candidates, which turns a linear scan into a logarithmic process.

Once that invariant is clear, the rest becomes much easier: exact search, insertion points, lower bounds, upper bounds, and even binary search on answers all follow the same pattern.

Try It Yourself

Use the interactive visualizer below to compare found vs missing targets, watch the midpoint move, and see how quickly the highlighted interval collapses.