Binary Search

Binary search finds a value in a sorted list without looking at every entry. It checks the middle, decides from that comparison which half can contain the value, and throws the other half away.

It is exactly how you look up a name in a phone book: open it, compare, continue in front or behind. For a million entries twenty comparisons are enough.

The search range is described by two boundaries, low and high. As long as it contains at least one element, this repeats:

1. Determine the middle of the current range.
2. If the value there is the one you want, the search is over.
3. If it is smaller than the wanted value, the target can only be on the right, so low moves behind the middle.
4. Otherwise high moves in front of the middle.

Once the boundaries cross, the range is empty and the value does not occur.

Because the range halves with every step, it takes at most log₂ n steps: 10 steps for 1,000 values, 20 for a million, 30 for a billion.

public static class BinarySearch
{
    // Returns the index of the value inside the sorted array, or -1 if it does not occur.
    public static int IndexOf(int[] sortedNumbers, int value)
    {
        var low = 0;
        var high = sortedNumbers.Length - 1;

        // Runs as long as the search window still contains at least one element.
        while (low <= high)
        {
            // Written this way instead of (low + high) / 2 so that it cannot overflow.
            var middle = low + (high - low) / 2;
            var current = sortedNumbers[middle];

            if (current == value)
                return middle;

            // The array is sorted, so the value can only be in one of the two halves.
            // The other half is dropped and the window halves with every step.
            if (current < value)
                low = middle + 1;
            else
                high = middle - 1;
        }

        return -1;
    }
}

// The array has to be sorted - that is the whole point of the algorithm.
var numbers = new[] { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };

Console.WriteLine(BinarySearch.IndexOf(numbers, 23));
Console.WriteLine(BinarySearch.IndexOf(numbers, 42));

5
-1

• The list has to be sorted. If it is not, the algorithm returns wrong results without noticing.
• The middle is calculated as low + (high - low) / 2 and not as (low + high) / 2. With very large indices the sum could otherwise overflow. That bug sat in widely used libraries for years.
• .NET ships this as Array.BinarySearch. On a hit it returns the index, otherwise the bitwise complement of the insertion position.