Binary Search: Iterative and Recursive in Java

Binary search is famously easy to describe and hard to write correctly. The reference implementation in Java’s own library carried an overflow bug for nine years, and the two conditions most often got wrong, the loop test and the midpoint, are each a single character.

Written against Java 17.

The iterative version

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

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (sorted[mid] == target)      return mid;
        else if (sorted[mid] < target)  low = mid + 1;
        else                            high = mid - 1;
    }
    return -(low + 1);            // not found; low is the insertion point
}

O(log n) time, O(1) space. Four details carry the correctness.

low <= high, not low < high. When the two converge on a single element, low == high, and that element has not been examined yet. With <, a one-element search space is skipped and the target is missed whenever it happens to land there: a bug that passes most tests and fails on the first and last elements.

low + (high - low) / 2, not (low + high) / 2. With arrays near Integer.MAX_VALUE / 2 in length the sum overflows to a negative number and the index throws. This is the bug that sat in java.util.Arrays.binarySearch from Java 1.2 until 2006, and it is invisible at every size anyone tests. (low + high) >>> 2, the unsigned shift, is the other correct form.

mid + 1 and mid - 1, not mid. sorted[mid] has just been compared and excluded, so including it again means the search space can stop shrinking. high = mid in the third branch is an infinite loop when low and high are adjacent.

The return value. -(low + 1) rather than a bare -1 encodes where the target would go. The offset by one exists because index 0 would otherwise be indistinguishable from a match at 0. This is what Arrays.binarySearch returns, and it is what makes “insert in order” a one-liner:

int idx = binarySearch(sorted, value);
int insertAt = idx >= 0 ? idx : -(idx + 1);

The recursive version

static int binarySearch(int[] sorted, int target) {
    return search(sorted, target, 0, sorted.length - 1);
}

private static int search(int[] sorted, int target, int low, int high) {
    if (low > high) return -(low + 1);

    int mid = low + (high - low) / 2;

    if (sorted[mid] == target)     return mid;
    if (sorted[mid] < target)      return search(sorted, target, mid + 1, high);
    return search(sorted, target, low, mid - 1);
}

Identical logic; the loop becomes the recursion and low > high becomes the base case.

The recursion depth is O(log n), so about 31 frames for a maximal int[], no stack risk. Both calls are in tail position, so a language with tail-call elimination would compile this to the loop; the JVM does not, so the recursive form is marginally slower and allocates frames.

Prefer the iterative version. The recursion is worth writing once for the exercise and offers nothing afterwards.

Duplicates: find the first, not any

Plain binary search returns an index of a matching element, unspecified which. With duplicates that is rarely what is wanted:

static int firstOccurrence(int[] sorted, int target) {
    int low = 0, high = sorted.length - 1, result = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (sorted[mid] == target) {
            result = mid;
            high = mid - 1;          // keep going LEFT
        } else if (sorted[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

The change is one line: on a match, record it and keep searching the left half instead of returning. low = mid + 1 in that branch gives the last occurrence instead.

The two together count occurrences in O(log n):

int count = lastOccurrence(a, t) - firstOccurrence(a, t) + 1;   // 0 if first is -1

The bounds formulation

An alternative shape avoids the equality branch entirely and is easier to adapt:

// smallest index with sorted[i] >= target
static int lowerBound(int[] sorted, int target) {
    int low = 0, high = sorted.length;         // note: length, not length - 1

    while (low < high) {                        // note: <, not <=
        int mid = low + (high - low) / 2;
        if (sorted[mid] < target) low = mid + 1;
        else                      high = mid;   // note: mid, not mid - 1
    }
    return low;                                 // in [0, length]
}

Three differences from the classic version, and they are consistent with each other: a half-open range [low, high) means high starts at length, the loop runs while the range is non-empty (<), and high = mid is correct because mid is excluded by the half-open convention.

This never returns “not found”. It returns the partition point, and sorted[low] == target tests membership. upperBound is the same with <= in the comparison.

Mixing the two conventions is where off-by-one errors come from. Pick one per codebase.

Use the library

int idx = Arrays.binarySearch(array, target);
int idx2 = Arrays.binarySearch(array, fromIndex, toIndex, target);
int idx3 = Collections.binarySearch(list, target);
int idx4 = Collections.binarySearch(list, target, comparator);

Overflow-safe since 2006, and the same -(insertionPoint + 1) on failure. Two constraints the Javadoc states and callers forget: the array must already be sorted, an unsorted input gives an undefined result rather than an error, and with duplicates the index returned is unspecified.

Collections.binarySearch on a LinkedList is O(n log n), not O(log n), because each midpoint access walks the list. It detects this and falls back to a linear scan above a threshold, which is better and still not what you wanted.

When binary search is the wrong tool

It needs random access and sorted data. Neither is free.

Sorting to enable one search costs O(n log n), worse than the O(n) linear scan it replaces. It pays off across many searches on stable data, which is the actual precondition.

On changing data, a TreeMap or a TreeSet keeps the ordering as writes happen and offers floorKey and ceilingKey, which are the same nearest-match question with the bookkeeping handled.

And for exact-match lookup with no ordering requirement, a HashMap is O(1) and needs no sort at all.

Beyond arrays

The pattern generalises to any monotonic predicate: “false, false, …, false, true, true” — where the answer is the boundary:

// smallest capacity that completes the work within the limit
static int minCapacity(int lo, int hi, IntPredicate feasible) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible.test(mid)) hi = mid;
        else                    lo = mid + 1;
    }
    return lo;
}

That is “binary search on the answer”, and it is what solves capacity, rate and threshold problems that mention no array at all. The precondition is only that the predicate flips once.

Related: searching a rotated sorted array and finding its minimum. More in the algorithms guides.

Frequently asked questions

Why is the loop condition low <= high?

When they converge, low == high and that element has not been checked. With <, a single-element range is skipped and the target is missed.

Why not (low + high) / 2?

It overflows to a negative index on very large arrays. Use low + (high - low) / 2 or (low + high) >>> 1. Java’s own library carried this bug for nine years.

Why mid + 1 and mid - 1?

sorted[mid] has been compared and excluded. Reusing mid as a bound means the range can stop shrinking, which is an infinite loop.

What does a negative return value mean?

-(insertionPoint + 1). The offset exists so a failed search at index 0 is distinguishable from a match at index 0.

Iterative or recursive?

Iterative. The logic is identical, the depth is only about 31 frames, and the JVM does not eliminate the tail call, so the recursion allocates for nothing.

How do I find the first of several equal elements?

On a match, record the index and continue into the left half rather than returning. Continuing right gives the last occurrence.

What is the lower-bound formulation?

A half-open range [low, high) with high = length, while (low < high) and high = mid. It returns the partition point rather than a “not found” sentinel and adapts more easily.

Can I binary search an unsorted array?

No. The result is undefined rather than an error, which is worse than a failure. It returns a plausible index.

Is Collections.binarySearch fast on a LinkedList?

No. Each midpoint access walks the list, making it O(n log n). It falls back to a linear scan above a threshold.

Where else does binary search apply?

Any monotonic predicate, the smallest value for which a condition becomes true. That solves capacity and threshold problems with no array involved.