Binary search

The idea

Compare the target with the middle element. If it is smaller, search the left half. If it is larger, search the right half. Repeat until the value is found or the search interval is empty.

Precondition: the array must be sorted in ascending order.

Keep two indices, low and high. They describe the inclusive interval that could still contain the target. Everything outside that interval has already been ruled out.

A worked example

Search for 23 in the array below.

Since 23 is greater than 12, discard indices 0 through 3. The remaining interval contains [16, 23, 38]. Its middle value is 23, so return index 5 in the original array.

Time complexity

Each unsuccessful comparison removes at least half the current candidates, up to rounding. The worst-case running time is $O(\log n)$ for nonempty arrays, and the iterative algorithm uses $O(1)$ extra space.

Implementation

This Java method returns an index containing the target, or -1 if the target is absent. It assumes a non-null sorted array. With duplicates, it returns a matching index, not necessarily the first.

static int binarySearch(int[] a, int target) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

The midpoint calculation avoids adding two potentially large indices. Moving past mid ensures that the interval shrinks on every unsuccessful comparison.

Try it yourself

Which values remain after the first comparison when the target is 5? What happens when the input array is empty?