Binary search

Binary search finds a value in a sorted array by repeatedly comparing with the middle element and discarding the half that cannot contain it. It needs about log2(n) steps: 20 comparisons for a million items.

A mental model

Guess my number between 1 and 100: always guess the middle and I answer "higher" or "lower". Seven guesses are enough.

How it works

Keep two bounds lo and hi. While lo <= hi: mid = lo + (hi - lo) / 2; if a[mid] == target return it; if it is smaller, lo = mid + 1; otherwise hi = mid - 1. If the loop ends, the value is absent.

The standard library does it for you: Arrays.binarySearch(a, key) and Collections.binarySearch(list, key). A negative result -(insertionPoint) - 1 means "not found, would go here".

The data must be sorted by the same ordering. The idea also works on any monotonic condition ("smallest x such that f(x) is true"): shipping capacity, square roots, first bad version.

Going deeper

Off-by-one errors are the main risk: decide whether hi is inclusive or exclusive and keep it consistent in the loop condition and updates. Test with empty, one element, two elements, first, last and missing.

Compute the middle as lo + (hi - lo) / 2 or (lo + hi) >>> 1: (lo + hi) / 2 overflows for large indexes (a bug that lived in the JDK for nine years).

With duplicates, a plain search returns any matching position; for the first or last occurrence continue narrowing after a hit.

On a LinkedList binary search is O(n) because reaching the middle costs a walk. Use ArrayList or an array.

Under the hood

Each iteration halves the search interval, so n elements need at most floor(log2 n) + 1 comparisons. Arrays.binarySearch is exactly this loop over the array, with a comparator variant for objects.

Common mistakes

• Searching an unsorted array.
• Infinite loop from lo = mid instead of mid + 1.
• Overflow in (lo + hi) / 2.
• Misreading the negative return value.