How do you write a correct binary search on an array list, including first and last occurrence?

A public candidate review of a Zalando live-coding round mentions "binary search on an array list". It sounds easy, which is why interviewers use it: the bugs are in the boundaries.

State the invariant first. Classic search with inclusive bounds: if the key is present, it is within [lo, hi]. Lower bound with half-open bounds: everything before lo is smaller than the key and everything from hi on is at least the key. Mixing the two styles in one loop is where off-by-one errors come from.

The overflow bug. Google's research blog showed that int mid = (low + high) / 2, used in many textbook and library implementations, fails when low + high exceeds Integer.MAX_VALUE; it recommends low + ((high - low) / 2) or (low + high) >>> 1.

import java.util.*;

public class BinarySearchDemo {
    // Index of key in a sorted list, or -1. Works on any RandomAccess list such as ArrayList.
    static int indexOf(List<Integer> a, int key) {
        int lo = 0, hi = a.size() - 1;            // inclusive bounds
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;            // no int overflow
            int v = a.get(mid);
            if (v < key) lo = mid + 1;
            else if (v > key) hi = mid - 1;
            else return mid;
        }
        return -1;
    }

    // First index i with a.get(i) >= key (a "lower bound"); a.size() if none.
    static int lowerBound(List<Integer> a, int key) {
        int lo = 0, hi = a.size();                // half-open [lo, hi)
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a.get(mid) < key) lo = mid + 1; else hi = mid;
        }
        return lo;
    }

    static int firstOccurrence(List<Integer> a, int key) {
        int i = lowerBound(a, key);
        return (i < a.size() && a.get(i) == key) ? i : -1;
    }

    static int lastOccurrence(List<Integer> a, int key) {
        int i = lowerBound(a, key + 1) - 1;       // assumes key < Integer.MAX_VALUE
        return (i >= 0 && a.get(i) == key) ? i : -1;
    }

    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>(List.of(1, 3, 3, 3, 7, 9));
        System.out.println(indexOf(a, 7));          // 4
        System.out.println(indexOf(a, 4));          // -1
        System.out.println(firstOccurrence(a, 3));  // 1
        System.out.println(lastOccurrence(a, 3));   // 3
        System.out.println(lowerBound(a, 8));       // 5
        System.out.println(indexOf(List.of(), 1));  // -1
        System.out.println(Collections.binarySearch(a, 4)); // -5: insertion point is 4
    }
}

Verified with OpenJDK 21.0.13: it prints 4, -1, 1, 3, 5, -1 and -5.

Why "array list" matters. ArrayList implements RandomAccess, so get(i) is constant time and the search is O(log n). The Collections.binarySearch Javadoc spells out the alternative: for a large list that does not implement RandomAccess, such as LinkedList, it does an iterator-based search with O(n) link traversals and O(log n) comparisons. Mentioning this shows you know the library, not just the algorithm.

Library behaviour worth knowing. Collections.binarySearch and Arrays.binarySearch return the index if found, otherwise -(insertion point) - 1, so the result is non-negative only when the key exists. With duplicates, the Javadoc gives no guarantee which matching index is returned, which is exactly why first and last occurrence need the lower-bound version. The list must be sorted by the same order you search with; otherwise the result is undefined.

Tests to say out loud. Empty list, one element, key smaller than all and larger than all, key absent between two elements, all elements equal, and duplicates at both ends.

Alternate interview scenarios