Binary Search in Less Than a Minute

A simple algorithm whose correctness depends on precise invariants.

Context

Binary search is often treated as trivial, yet it is a common source of off-by-one bugs and infinite loops. The difficulty is not the idea, but maintaining correct boundaries.

Core idea

Binary search finds an element in a sorted array by repeatedly halving the search space. Its time complexity is O(log n).

The algorithm operates on a half-open interval [lo, hi):

• lo is inclusive
• hi is exclusive

The invariant is simple and strict:

If the target exists, it is always inside [lo, hi).

On each iteration:

• Compute the middle index
• Compare the middle value to the target
• Shrink the interval while preserving the invariant

When lo == hi, the interval is empty. If the target was not found earlier, it does not exist in the array.

Implementation

class BinarySearch {
    static int search(int[] haystack, int needle) {
        if (haystack.length == 0) return -1;
    
        var lo = 0;
        var hi = haystack.length;
        
        while (lo < hi) {
            var mid = lo + (hi - lo) / 2;
            var value = haystack[m];
            
            if (value == needle) {
                return mid;
            } else if (value < needle) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        return -1;
    }
}