Binary Search¶

Binary search repeatedly discards half of a sorted, random-access search range. It does not sort its input.

Contract¶

Precondition: values is sorted in nondecreasing order.
Output: an index containing target, or -1 if absent.
When duplicates exist, this basic version may return any matching index.

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

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

The midpoint expression avoids the addition overflow possible in (low + high) / 2.

Correctness¶

Use the invariant: if the target occurs, at least one occurrence is inside the inclusive range [low, high]. Sorted order justifies discarding the half that cannot contain the target. The range strictly shrinks. If it becomes empty, no occurrence exists.

Complexity¶

Each iteration halves the candidate range, giving worst-case Θ(log n) time and Θ(1) auxiliary space. Sorting first would usually cost Ω(n log n) and would change positions, so it is a separate preprocessing decision.

Exercises¶

Return the first matching index among duplicates.
Implement a half-open range [low, high) version.
State what fails if the array is not sorted.