Binary search

Why the array must be sorted

When the middle value is smaller than the target, every value to its left is also too small. We can discard that entire part. If the array is not sorted, this reasoning fails. The player rejects unsorted input instead of silently sorting it.

Sorting a fresh array just to perform one search usually costs more than a linear scan. Binary search is useful when data is already sorted or you perform many searches on the same sorted data.

The invariant: a candidate and a closed interval

The remaining search interval includes both boundaries: [low, high]. All indices before low contain values smaller than the target. A candidate is an equal value already found; there may still be an earlier equal value inside the interval.

If values[mid] < target, set low = mid + 1. Otherwise set high = mid − 1; first save mid as the candidate when the values are equal. Every step removes mid and at least half of the current interval. When low > high, return the candidate or −1.

Example: repeated sixes

In the default 16-element array, the first middle index is 7 and its value is 6. Save index 7, but do not stop: an earlier 6 may exist. Inspect indices 3, 5 and 4 next. Index 5 is the answer after four inspected elements.

Try target 7 for a missing value, −8 for the first element, or 34 for the last. An empty array returns −1 without inspecting any elements. The counter counts inspected middle elements, not individual JavaScript comparison operators.

Time and memory

Worst-case and average time are O(log n); empty input takes O(1). This first-occurrence variant keeps searching after equality, so finding an equal value in the middle does not imply immediate completion. The iterative search uses O(1) auxiliary memory and does not change the array.

The visualization copies the input once and shares that frozen array between immutable snapshots. Its stored history costs O(n + log n), separately from the algorithm. Input validation takes O(n). Stability is a property of sorting; this search does not rearrange equal elements.

JavaScript implementation

The function below has the same boundaries, midpoint and duplicate handling as the visualization. It expects a sorted array of finite numbers and a finite target. The result is a zero-based index, or −1 when no value matches.

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

What AlgiViz does here

The algorithm and its states belong to this website. AlgiViz supplies immutable step wrappers, timeline sampling and scene rendering. Playback can revisit any saved step without running the search again. The canvas uses discrete highlights, so no motion is required to understand a step.