Binary search

↑

Binary search finds a value in a sorted array by examining the middle element. Each comparison can remove about half the remaining candidates.

Try each step

INTERACTIVE / LIVE

Binary search stepper

Pick a target, step forward and watch the search range change.

Live demo

Implementations in C# and C++

static int BinarySearch(int[] sorted, int target)
{
    int left = 0;
    int right = sorted.Length - 1;

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

        if (sorted[middle] == target)
            return middle;

        if (sorted[middle] < target)
            left = middle + 1;
        else
            right = middle - 1;
    }

    return -1;
}

#include <vector>
int binarySearch(const std::vector<int>& sorted, int target) {
    int left = 0, right = static_cast<int>(sorted.size()) - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (sorted[mid] == target) return mid;
        if (sorted[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

The time complexity is O(log n) and this iterative implementation uses O(1) additional space.

Why the search interval shrinks

Binary search works by maintaining an invariant: if the target is present, it is still in the current [left, right] interval. When the middle value is too small, everything at or before the middle can be removed. When it is too large, everything at or after the middle can be removed. Each step preserves the invariant and reduces the remaining candidates.

Common off-by-one errors

Be explicit about whether your right boundary is inclusive or exclusive. An inclusive version starts with right = length - 1 and loops while left <= right; a half-open version starts with right = length and loops while left < right. Both work, but mixing the conventions can skip the last item or produce an infinite loop.

Test more than the middle

Check an empty input, a single item, the first and last positions, absent targets below and above the array’s range, and repeated values. A basic binary search may return any matching duplicate rather than the first. If you need a lower or upper bound, implement that requirement explicitly.

Check your understanding

CHECK YOUR UNDERSTANDING

What must be true for binary search to work correctly?

Show the explanation

Ordering lets us know which half cannot contain the target.