Binary Search Visualization

Finding elements by cutting the problem in half

Binary search finds any element in a sorted array by repeatedly halving the search space. What makes it remarkable isn't the elegance — it's the impossibility of linear alternatives. A million elements becomes twenty comparisons. But the halving is invisible in prose. You have to watch the bounds collapse to feel why logarithmic time is fundamentally different from any other kind of speed.

The Sorted Array

Binary search only works on sorted arrays. Each step compares the target against the middle element, then discards half the remaining range. The visual shows this directly: the unexamined elements dim, the active range stays bright, and the midpoint jumps with each comparison.

const array = [];
for (let i = 0; i < 20; i++) {
  array.push(Math.floor(Math.random() * 100) + 1);
}
array.sort((a, b) => a - b);

The array has 20 elements, values 1-100, sorted ascending. Twenty elements is small enough to see every position, large enough that binary search still beats linear. A linear search could require up to 20 comparisons; binary search requires at most 5. The difference grows with size: a million elements becomes at most 20 comparisons.

The Search Bounds

Two indices define the current search range: low and high. Initially, low is 0 (the first element) and high is array.length - 1 (the last element). Each comparison eliminates roughly half the remaining elements by moving either low up or high down.

let low = 0;
let high = array.length - 1;

const mid = Math.floor((low + high) / 2);

if (array[mid] < target) {
  low = mid + 1;  // target is in upper half
} else if (array[mid] > target) {
  high = mid - 1; // target is in lower half
} else {
  // found it
}

The midpoint calculation uses integer division to find the center. When the target is greater than the midpoint, we know it cannot be anywhere below mid, so we move low to mid + 1. When the target is smaller, we move high down. The range shrinks from both ends until either the target is found or low exceeds high — meaning the target isn't in the array.

The Halving Strategy

Binary search works because each comparison eliminates half the remaining search space. This isn't a linear speedup — it's geometric. If the array has 20 elements, the first comparison eliminates 10. The second eliminates 5. The third eliminates 2 or 3. By the fifth comparison, you're guaranteed to have either found the target or exhausted the array.

// After comparing with midpoint:
if (array[mid] < target) {
  low = mid + 1;  // All elements 0..mid are now impossible
} else {
  high = mid - 1; // All elements mid..end are now impossible
}
// The eliminated range is roughly half of what remained

This halving is why binary search is called a "divide and conquer" algorithm. The problem space shrinks exponentially, not linearly. A million-element array requires at most 20 comparisons because 2²⁰ ≈ 1,048,576 — the logarithm base 2 of the size tells you exactly how many halvings fit before you run out of elements.

The Comparison Counter

Each call to the comparison step increments a counter. This counter is the visual proof of logarithmic time. Watch how few comparisons are needed even when the target is at the edges. Try finding the first or last element — still just a few steps.

let comparisons = 0;

function step() {
  comparisons++;
  const mid = Math.floor((low + high) / 2);
  
  if (array[mid] === target) {
    found = true;
    foundIndex = mid;
  } else if (array[mid] < target) {
    low = mid + 1;
  } else {
    high = mid - 1;
  }
}

The counter accumulates across steps. When the target is found, the counter stops. If you run the algorithm to completion with "Run", notice how the final count never exceeds ceil(log₂(n)) where n is array length — for 20 elements, that's 5. For a million elements, 20.

Time Complexity Visual

The visual makes time complexity tangible. Linear search would check each element in order: at worst, it visits all 20 positions. Binary search visits at most 5. The difference isn't merely 4x faster — it's the difference between visiting every element and visiting only the square root of that number in logarithmic terms.

// Linear search: O(n)
for (let i = 0; i < array.length; i++) {
  if (array[i] === target) return i;
}

// Binary search: O(log n)
// 20 elements → max 5 comparisons
// 1,000,000 elements → max 20 comparisons
// 1,000,000,000 elements → max 30 comparisons
// The logarithm grows agonizingly slowly

Click "Random" to pick a target that exists in the array, then "Run" to watch the count. The comparisons counter will show 3, 4, maybe 5 steps at most — never close to 20. Now imagine the array had a billion elements. Binary search still finishes in at most 30 comparisons. A linear search would visit up to a billion. This is why logarithmic algorithms matter at scale: the cost barely grows even as the input explodes.

Visual Representation

The canvas shows the array as a row of cells. Each cell contains its value. The active range (low to high) is drawn with full brightness. Elements outside the range are dimmed. The midpoint is highlighted in a distinct color. When the target is found, that cell lights up. If the target isn't found, the whole array dims to show the failed search.

function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  
  for (let i = 0; i < array.length; i++) {
    const inRange = i >= low && i <= high;
    const isMid = i === mid;
    const isFound = found && i === foundIndex;
    
    // Set color based on state
    if (isFound) {
      ctx.fillStyle = '#22c55e'; // green for found
    } else if (isMid) {
      ctx.fillStyle = '#f59e0b'; // amber for midpoint
    } else if (inRange) {
      ctx.fillStyle = '#14b8a6'; // teal for in-range
    } else {
      ctx.fillStyle = '#374151'; // dim gray for eliminated
    }
    
    drawCell(i, array[i]);
  }
}

The color progression tells the story: bright elements are still candidates, dimmed elements have been eliminated, the amber cell is the current midpoint under examination, and green marks success. The visual shrinking of the active range makes the halving tangible in a way that code alone cannot.

What This Reveals

Binary search demonstrates a fundamental principle: logarithmic algorithms stay fast even as input size explodes. The intuition is geometric — each step cuts the problem in half, so the number of steps grows with the logarithm of size, not linearly with size. A billion-element array requires at most 30 comparisons. The visualization makes this concrete by showing exactly how few steps are needed, regardless of where the target hides. But there's a deeper lesson: the power comes entirely from the sorted structure. An unsorted array offers no purchase for halving. The cost of sorting is paid once, then binary search reaps the benefit forever. This is the design tradeoff: invest in structure that enables fast operations, or accept slow operations on unstructured data. Binary search is the canonical example of structure paying dividends.