Binary Search Visualization — Step by Step

Start with two pointers around the whole array

Binary Search keeps a live search range defined by two indices: low at the left edge and high at the right edge. Everything between them might contain the target; everything outside has been proven not to. Take the sorted array [3, 7, 12, 18, 25, 31, 42, 50] and search for 42. Initially low = 0 and high = 7 — all eight elements are candidates. The single precondition is that the array is sorted: the whole algorithm is built on the fact that comparing one element tells you which *side* of it the target must be on.

Check the midpoint and throw away half

Compute the midpoint: mid = ⌊(low + high) / 2⌋ = ⌊(0 + 7) / 2⌋ = 3, where the value is 18. Compare it with the target: 18 < 42. Because the array is sorted, the target cannot be at index 3 or anywhere to its left — indices 0 through 3 are eliminated in one comparison. Set low = mid + 1 = 4. Four elements gone, four remain: [25, 31, 42, 50]. This is the whole trick — each comparison discards half of whatever is left, no matter how large the array is.

Repeat until the range collapses on the target

Second iteration: the range is [4..7], so mid = ⌊(4 + 7) / 2⌋ = 5, value 31. Since 31 < 42, eliminate the left portion again: low = 6. Third iteration: range [6..7], mid = 6, value 42 — a match! The search finishes at index 6 after just 3 comparisons. A linear search scanning the same array would have needed 7. Watch this in the visualizer: the highlighted range shrinks by half each step, and eliminated elements gray out.

Why it is O(log n)

Each comparison halves the candidates: 8 → 4 → 2 → 1, so 8 elements need at most ⌈log₂ 8⌉ + 1 ≈ 4 checks. The payoff grows absurdly with size: 1,000 elements need about 10 comparisons, 1,000,000 need about 20, and a billion need about 30. Doubling the array adds exactly one comparison. That is what O(log n) means in practice — the work grows with the number of times you can halve n, not with n itself. It is the same halving idea that powers binary search trees.

When the target is missing

Search the same array for 20. Range [0..7], mid value 18 < 20 → low = 4. Range [4..7], mid value 31 > 20 → high = 4. Range [4..4], mid value 25 > 20 → high = 3. Now low = 4 and high = 3 — the pointers have crossed, meaning the range is empty and no element can equal 20. The loop condition low <= high fails and the search reports not-found. Usefully, low now points at index 4, exactly where 20 *would* be inserted to keep the array sorted — many libraries expose this as the insertion point.

JavaScript

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

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

    if (arr[mid] === target) {
      return mid; // found
    }
    if (arr[mid] < target) {
      low = mid + 1; // target is in the right half
    } else {
      high = mid - 1; // target is in the left half
    }
  }
  return -1; // pointers crossed: not present
}

Python

def binary_search(arr, target):
    """Return the index of target in sorted arr, or -1 if absent."""
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            low = mid + 1   # target is in the right half
        else:
            high = mid - 1  # target is in the left half

    return -1  # not found (low is the insertion point)

Java

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            // low + (high - low) / 2 avoids int overflow
            int mid = low + (high - low) / 2;

            if (arr[mid] == target) {
                return mid;
            }
            if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1; // not found
    }
}