Search in a Sorted Array

The classic template

To search for one exact value, it is convenient to keep a closed range [left, right]. As long as the left boundary has not passed the right one, the range still contains unchecked candidates.

static int binarySearch(int[] values, int target) {
    int left = 0;
    int right = values.length - 1;

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

        if (values[mid] == target) {
            return mid;
        }
        if (values[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

If the middle value is smaller than the target, position mid is definitely unsuitable, so the new left boundary is mid + 1. If the middle value is larger than the target, mid - 1 is used symmetrically.

Why compute mid this way

The expression left + (right - left) / 2 represents the same midpoint as (left + right) / 2, but it does not require adding two potentially large indexes first. It is a safe template worth using by habit.

What if target appears several times

This version guarantees that it returns some position containing the target, but it does not promise the first or the last one. To find a specific boundary, the stopping condition and the way the range shrinks must change; that is the next idea we will study.