11.1 Binary Search and Boundaries

Prerequisites: Sorting. This lesson progresses from exact search to left and right boundaries, then covers rotated arrays. Ordinary searches use nondecreasing int[] arrays. Rotated search requires an originally strictly increasing array cyclically shifted at any split point. Functions leave arrays unchanged, require non-null input, and do not revalidate sorting before each query. Results are unspecified when those preconditions fail.

Binary search is most commonly misapplied by confusing the interval model, taking the midpoint is just one step in the process. This page divides into two categories:

• Exact search uses a closed interval [left, right], with the loop condition being left <= right;
• Boundary search uses a left-closed, right-open interval [left, right), with the loop condition being left < right.

Before writing code, clearly define what the function returns: "a position where the value equals the target," "the first position that is not less than the target," or "the first position that is greater than the target." These three questions must not be conflated into a vague statement like "find target."

A Compilable Boundary Implementation

import java.util.Arrays;

public final class BinarySearchDemo {
    private BinarySearchDemo() {}

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

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

    // Return the first i with values[i] >= target, or values.length if none exists.
    static int lowerBound(int[] values, int target) {
        int left = 0;
        int right = values.length;

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

    // Return the first i with values[i] > target, or values.length if none exists.
    static int upperBound(int[] values, int target) {
        int left = 0;
        int right = values.length;

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

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

        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (values[middle] == target) {
                return middle;
            }

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

    public static void main(String[] args) {
        int[] values = {1, 2, 4, 4, 4, 5, 6};

        assert search(values, 4) >= 2 && search(values, 4) <= 4;
        assert search(values, 7) == -1;
        assert lowerBound(values, 4) == 2;
        assert upperBound(values, 4) == 5;
        assert lowerBound(values, 0) == 0;
        assert lowerBound(values, 7) == values.length;
        assert upperBound(new int[0], 3) == 0;

        int[] rotated = {4, 5, 6, 7, 0, 1, 2};
        assert searchRotatedDistinct(rotated, 0) == 4;
        assert searchRotatedDistinct(rotated, 3) == -1;

        System.out.println(Arrays.toString(values));
        System.out.println("Range of 4: [" + lowerBound(values, 4)
                + ", " + upperBound(values, 4) + ")");
    }
}

To enable Java assertions at runtime:

javac BinarySearchDemo.java
java -ea BinarySearchDemo

The complete output is:

[1, 2, 4, 4, 4, 5, 6]
Range of 4: [2, 5)

The interval [2, 5) indicates that the values at indices 2, 3, and 4 are equal to the target. A precise search only guarantees returning one matching position; if the use case requires counting duplicate values, the difference between the upper and lower bounds should be used:

count(target) = upperBound(values, target) - lowerBound(values, target)

Using Invariants to Verify Contraction Direction

The goal of lowerBound is to find the position of the first >= target. Throughout the loop, the following invariants must hold:

• All elements in [0, left) are guaranteed to be strictly less than the target;
• All elements in [right, n) are guaranteed to be strictly greater than or equal to the target;
• The undecided range is [left, right).

When left == right, the undecided range is empty, and the boundary point is the correct answer. This return contract holds even in edge cases (such as when the target is smaller than all elements, larger than all elements, or when the array is empty) so no additional branching is needed.

upperBound simply changes the condition from < target to <= target, resulting in the first position strictly greater than the target. The position of the last <= target element can be expressed as upperBound(...) - 1, though the result may be -1, and the caller must handle this boundary case.

The midpoint is written as left + (right - left) / 2, which prevents overflow of left + right within the Java int range. Here indices are nonnegative and left <= right, so the difference also fits in an int. For an arbitrary integer interval spanning negative and positive endpoints, right-left can itself overflow and may require a wider type.

Why a Rotated Array Can Still Be Halved

In a strictly increasing array, after a cyclic shift at any split point, for example:

[0, 1, 2, 4, 5, 6, 7] -> [4, 5, 6, 7, 0, 1, 2]

at least half of the array remains strictly ordered. The algorithm first checks whether the left half is ordered, then verifies if the target lies within a closed-open range of that half. If not, it shifts to the other half.

This page explicitly requires that keys be distinct. If duplicates are allowed in large quantities, values[left] == values[middle] == values[right] may fail to determine which half is ordered, forcing a gradual boundary shrinkage. In the worst case, the time complexity degrades to O(n). Avoid using the distinct-key version when the interface does not specify how duplicates are handled.

Complexity and Applicability Boundaries

Problem	Time	Extra Space	Premise
Exact Binary Search	O(log n)	O(1)	Sorted array
Lower / Upper Bound Search	O(log n)	O(1)	Sorted array
Rotated array with distinct keys	O(log n)	O(1)	Strictly increasing array shifted at any split point, including no shift
Rotated array with duplicates allowed	Worst-case O(n)	O(1)	Requires special handling of ambiguous intervals

The logarithmic bounds describe growing input sizes; empty and single-element arrays take constant work. A returned boundary n is a valid insertion point, but not a readable array index. Check it before indexing.

If data is continuously inserted or deleted, maintaining a sorted array may require O(n) element shifts. In such cases, the query frequency, update frequency, and data structure design should be evaluated together. Binary search only analyzes the positioning within an already-accessible, sorted sequence.

Java Arrays.binarySearch returns -(insertionPoint+1) on a miss; this page's search always returns -1. Searching for 3 in [1,2,4] has insertion point 2, so the library returns -3. Decode a negative result r with -(r+1). A hit among duplicates does not promise the first occurrence. See Java Arrays.binarySearch.

Check Search Boundaries

1. Manually calculate lowerBound for empty arrays, single-element arrays, and arrays where all elements are equal.
2. Use lowerBound == upperBound to determine whether a target is missing, and explain why this approach works.
3. Add random testing to the rotation array function: first generate a strictly increasing array, then pick an arbitrary rotation point.
4. If the requirement is to find the first position equal to target, how can lowerBound be reused and how should missing cases be handled?

Binary search relies on a continuously maintained invariant of the interval, rather than on the phrase "halve each time alone." When the interval model, contraction rules, and return contract are consistent, edge cases like empty arrays, duplicate values, and out-of-bounds insertion points naturally fall into the same logical framework.

The next lesson shifts the object of search from numbers to text, introducing Rabin–Karp, KMP, and Trie. Following that, we apply the same "reduce the problem" mindset to learn Divide and Conquer.