Binary search fundamentals

Binary search relies on one fact: if arr[mid] < target, then every element left of mid is also smaller, so the whole left half can be thrown away. That is only true when the array is sorted.

On unsorted data the algorithm still runs and returns an answer, but the answer can be wrong. It may report -1 for a value that is present.

Keep a closed window [lo, hi] that must contain the target if it exists. Probe mid, then move lo or hi past mid. The loop ends when the window is empty (lo > hi).

Compute mid as lo + (hi - lo) / 2. The naive (lo + hi) / 2 can overflow int for very large arrays. (lo + hi) >>> 1 is the other safe form.

• Each iteration at least halves the window, so there are at most ⌊log₂ n⌋ + 1 probes.
• The JDK provides Arrays.binarySearch(arr, key). It returns -(insertionPoint) - 1 when the key is missing.
• With duplicates, neither this code nor the JDK promises which matching index you get. Use first/last occurrence when it matters.

1public static int binarySearch(int[] arr, int target) {
2    int lo = 0, hi = arr.length - 1;
3    while (lo <= hi) {
4        int mid = lo + (hi - lo) / 2;
5        if (arr[mid] == target) {
6            return mid;
7        } else if (arr[mid] < target) {
8            lo = mid + 1;
9        } else {
10            hi = mid - 1;
11        }
12    }
13    return -1;
14}

The recursive version expresses the same idea directly: search the left half or the right half. The base case is an empty window.

Each call is a tail call, but Java does not eliminate tail calls, so recursion uses O(log n) stack frames. The animation's call-stack panel shows each frame being pushed and then returning the answer.

1public static int search(int[] arr, int target, int lo, int hi) {
2    if (lo > hi) {
3        return -1;
4    }
5    int mid = lo + (hi - lo) / 2;
6    if (arr[mid] == target) {
7        return mid;
8    }
9    if (arr[mid] < target) {
10        return search(arr, target, mid + 1, hi);
11    }
12    return search(arr, target, lo, mid - 1);
13}

Lower bound returns the first index i with arr[i] >= target. If every element is smaller, it returns arr.length. This is exactly where to insert the target to keep the array sorted, before any equal elements.

It uses a half-open window [lo, hi) starting at hi = arr.length. When arr[mid] >= target, mid could be the answer, so we set hi = mid rather than mid - 1.

• Number of elements smaller than x: lowerBound(arr, x).
• Does x exist? i < n && arr[i] == x where i = lowerBound(arr, x).
• C++ std::lower_bound and Java TreeSet.ceiling answer the same question.

1public static int lowerBound(int[] arr, int target) {
2    int lo = 0, hi = arr.length;      // half-open window [lo, hi)
3    while (lo < hi) {
4        int mid = lo + (hi - lo) / 2;
5        if (arr[mid] < target) {
6            lo = mid + 1;
7        } else {
8            hi = mid;
9        }
10    }
11    return lo;
12}

Upper bound returns the first index i with arr[i] > target. The only change from lower bound is < becoming <= in the comparison.

Together the two bounds answer counting questions in O(log n): the number of copies of x is upperBound(x) - lowerBound(x), and the number of values in [a, b] is upperBound(b) - lowerBound(a).

1public static int upperBound(int[] arr, int target) {
2    int lo = 0, hi = arr.length;      // half-open window [lo, hi)
3    while (lo < hi) {
4        int mid = lo + (hi - lo) / 2;
5        if (arr[mid] <= target) {
6            lo = mid + 1;
7        } else {
8            hi = mid;
9        }
10    }
11    return lo;
12}

To find the first copy of a value, do not stop at a match. Record it in ans and keep searching left. For the last copy, record it and keep searching right.

Both remain O(log n) even when every element is the same value. A linear scan outward from any match would degrade to O(n).

1public static int firstOccurrence(int[] arr, int target) {
2    int lo = 0, hi = arr.length - 1, ans = -1;
3    while (lo <= hi) {
4        int mid = lo + (hi - lo) / 2;
5        if (arr[mid] == target) {
6            ans = mid;                 // remember this match
7            hi = mid - 1;              // keep looking left
8        } else if (arr[mid] < target) {
9            lo = mid + 1;
10        } else {
11            hi = mid - 1;
12        }
13    }
14    return ans;
15}

1public static int lastOccurrence(int[] arr, int target) {
2    int lo = 0, hi = arr.length - 1, ans = -1;
3    while (lo <= hi) {
4        int mid = lo + (hi - lo) / 2;
5        if (arr[mid] == target) {
6            ans = mid;                 // remember this match
7            lo = mid + 1;              // keep looking right
8        } else if (arr[mid] < target) {
9            lo = mid + 1;
10        } else {
11            hi = mid - 1;
12        }
13    }
14    return ans;
15}