Binary Search

Category: Searching

The problem

This repo's Linear Search answers "is this here?" in O(n) because it can't assume anything about the data's order. If the data is already sorted — a common, cheap assumption once it's been sorted a single time — that O(n) is leaving an enormous amount of information on the table: every comparison against an unsorted collection tells you almost nothing about where else to look; a comparison against a sorted one tells you which entire half to discard.

The solution

Compare the target against the middle element. If it matches, done. If the target is smaller, the entire upper half can be discarded — every element there is guaranteed larger. If it's larger, discard the lower half. Repeat on whatever's left. Each comparison eliminates half the remaining candidates, which is what makes this O(log n): the search space shrinks geometrically, not linearly. Implemented iteratively with a shrinking [low, high] window rather than recursively, so a very large array never risks a stack frame per halving.

Classic example

classic/BinarySearch is generic over Comparator<? super T> — no Arrays.binarySearch shortcut. The loop shrinks a [low, high] window each iteration instead of recursing, which is what keeps this safe on arrays too large for a recursive call stack to handle comfortably. BinarySearchTest covers a target in the middle, at the start, at the end, a missing target, an empty array, a single-element array, every position of an even-sized array (exercises both midpoint-rounding directions), and both null-argument guards.

Applied example: BACEN PIX-key snapshot lookup

applied/RegisteredPixKeyLookup checks whether a PIX key is registered against a nightly, already-sorted snapshot of every registered key — the kind of batch export a reconciliation job pulls once and then queries many times over. Unlike a trie built incrementally as keys register in real time, this assumes the entire key set is already known and fixed for the day: sorting it once up front and binary searching it per lookup is cheaper than maintaining a live structure for data that doesn't change until tomorrow's snapshot. RegisteredPixKeyLookupTest covers a registered key, an unregistered key, and both null-argument guards.

Benchmark

./gradlew :searching:binary-search:jmh

Real run on this machine (JMH 1.37, JDK 26.0.2, 2 warmup + 3 measurement iterations, 1 fork). Same worst case, same sizes, same machine as this repo's Linear Search benchmark:

That's the O(log n) claim, made unmistakable: a 100x increase in size (100→10,000) costs only ~2.15x more time; a further 100x increase (10,000→1,000,000) costs only ~1.47x more — shrinking multipliers for the same proportional growth in data, exactly the signature of logarithmic scaling (log₂(10,000)/log₂(100) ≈ 2.0, log₂(1,000,000)/log₂(10,000) ≈ 1.5 — the predicted shape, matched almost exactly). Against Linear Search's 1,676,427.30 ns for the identical question at size=1,000,000, this module answers in 30.29 ns — ~55,353x faster, on the same machine, for the same "is it there" question. The only difference is one bit of information linear search doesn't get to use: the data is sorted.

When not to use it

• Data isn't sorted, and won't be queried enough times to justify sorting it once? This repo's Linear Search skips the sorting cost entirely — worth it only if the number of lookups stays small.
• Data changes frequently (frequent inserts/deletes) and needs to stay searchable at every step? Keeping an array sorted under churn costs O(n) per insert to maintain — a self-balancing tree structure (an AVL tree or a B-tree, for instance) keeps both operations fast instead of trading one for the other.
• Need the closest key, not just an exact match, or an ordered range? This implementation returns -1 on a miss and throws away exactly where the target would have gone — a floor/ ceiling-aware variant would need to return that boundary instead.

Test coverage

100% instruction coverage, 100% branch coverage (JaCoCo). Reproduce it yourself:

./gradlew :searching:binary-search:jacocoTestReport

Report at searching/binary-search/build/reports/jacoco/test/html/index.html.

Further reading

• Cormen, Leiserson, Rivest & Stein — Introduction to Algorithms (CLRS), 3rd/4th ed., Problem 2-4 covers search-related recurrences; binary search itself is a running example throughout the divide-and-conquer chapters.
• Sedgewick & Wayne — Algorithms, 4th ed., section 3.1, "Symbol Tables" — presents binary search as BinarySearch.rank, the baseline every ordered symbol table in the book improves on.

Unit tests

package com.algorithms.searching.binarysearch.classic;

import org.junit.jupiter.api.Test;

import java.util.Comparator;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class BinarySearchTest {

    @Test
    void findsATargetInTheMiddle() {
        Integer[] array = {1, 3, 5, 7, 9};

        int index = BinarySearch.search(array, 5, Comparator.naturalOrder());

        assertThat(index).isEqualTo(2);
    }

    @Test
    void findsATargetAtTheStart() {
        Integer[] array = {1, 3, 5, 7, 9};

        int index = BinarySearch.search(array, 1, Comparator.naturalOrder());

        assertThat(index).isZero();
    }

    @Test
    void findsATargetAtTheEnd() {
        Integer[] array = {1, 3, 5, 7, 9};

        int index = BinarySearch.search(array, 9, Comparator.naturalOrder());

        assertThat(index).isEqualTo(4);
    }

    @Test
    void returnsMinusOneWhenTheTargetIsMissing() {
        Integer[] array = {1, 3, 5, 7, 9};

        int index = BinarySearch.search(array, 4, Comparator.naturalOrder());

        assertThat(index).isEqualTo(-1);
    }

    @Test
    void returnsMinusOneOnAnEmptyArray() {
        Integer[] array = {};

        int index = BinarySearch.search(array, 1, Comparator.naturalOrder());

        assertThat(index).isEqualTo(-1);
    }

    @Test
    void singleElementArrayFindsItsOnlyElement() {
        Integer[] array = {42};

        int index = BinarySearch.search(array, 42, Comparator.naturalOrder());

        assertThat(index).isZero();
    }

    @Test
    void evenSizedArrayFindsEveryElement() {
        Integer[] array = {1, 2, 3, 4};

        for (int expected = 0; expected < array.length; expected++) {
            assertThat(BinarySearch.search(array, array[expected], Comparator.naturalOrder())).isEqualTo(expected);
        }
    }

    @Test
    void rejectsANullArray() {
        assertThatThrownBy(() -> BinarySearch.search(null, 1, Comparator.naturalOrder()))
                .isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsANullComparator() {
        assertThatThrownBy(() -> BinarySearch.search(new Integer[] {1}, 1, null))
                .isInstanceOf(IllegalArgumentException.class);
    }
}

package com.algorithms.searching.binarysearch.applied;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class RegisteredPixKeyLookupTest {

    @Test
    void reportsTrueForARegisteredKey() {
        RegisteredPixKeyLookup lookup = new RegisteredPixKeyLookup(
                new String[] {"alice@bank.com", "bob@bank.com", "carol@bank.com"});

        assertThat(lookup.isRegistered("bob@bank.com")).isTrue();
    }

    @Test
    void reportsFalseForAnUnregisteredKey() {
        RegisteredPixKeyLookup lookup = new RegisteredPixKeyLookup(
                new String[] {"alice@bank.com", "bob@bank.com", "carol@bank.com"});

        assertThat(lookup.isRegistered("dave@bank.com")).isFalse();
    }

    @Test
    void rejectsANullSnapshot() {
        assertThatThrownBy(() -> new RegisteredPixKeyLookup(null)).isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsANullKey() {
        RegisteredPixKeyLookup lookup = new RegisteredPixKeyLookup(new String[] {"alice@bank.com"});

        assertThatThrownBy(() -> lookup.isRegistered(null)).isInstanceOf(IllegalArgumentException.class);
    }
}

View full JaCoCo coverage report →