Binary Search

Suppose we have an array whose elements are in sorted order. Let’s turn the halving idea into code.

We have to keep track of a range of indices that could still contain the target. At the start that range is the whole array, from index 0 to index n - 1. At each step we look at the middle element of the range and compare it with the target. There are three cases.

  • If the middle element equals the target, we are done, and we return its index.
  • If the middle element is less than the target, the target cannot be at the middle or anywhere left of it, as explained earlier, so we throw away the left part and keep the range just to the right of the middle.
  • If the middle element is greater than the target, the same reasoning goes the other way, and we keep the range just to the left.

Each comparison throws away half of the range. We repeat until we find the target or the range becomes empty, and an empty range means the target is not in the array at all.

Here is a Java implementation of this idea. For simplicity, we run it on a regular array of integers.

public static int binarySearch(int[] arr, int target) {
  int low = 0;
  int high = arr.length - 1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    int cmp = Integer.compare(arr[mid], target);
    if (cmp == 0) {
      return mid;  // found it
    } else if (cmp < 0) {
      low = mid + 1;  // middle is too small; search the right half
    } else {
      high = mid - 1;  // middle is too big; search the left half
    }
  }
  return -1;  // range is empty: not present
}
Why not (low + high) / 2?

You may be tempted to calculate the midpoint as (low + high) / 2. That formula computes the correct midpoint, but in Java the sum low + high is computed as an int before the division, and on a very large array it can exceed Integer.MAX_VALUE and overflow into a negative number. Writing low + (high - low) / 2 gives the same midpoint without ever forming a value larger than high. Read it as “the start of the range plus half its length.” Java’s own built-in binary search shipped with the (low + high) / 2 bug and it went unnoticed for years.

Let’s trace it

Take the sorted array arr = [3, 9, 14, 21, 28, 33, 42, 55] and search for target = 42. We track three indices: low (L), high (R), and the mid (M) we compare against. The shaded ░ cells are the part of the array we have already ruled out. Watch how many cells get shaded after each comparison.

We start with the whole array in range.

   0    1    2    3    4    5    6    7
┌────┬────┬────┬────┬────┬────┬────┬────┐
│  3 │  9 │ 14 │ 21 │ 28 │ 33 │ 42 │ 55 │
└────┴────┴────┴────┴────┴────┴────┴────┘
   ↑              ↑                   ↑
   L              M                   R

The middle of 0..7 is index 3, and arr[3] = 21, which is less than 42. So the target must be to the right, and we discard everything from mid leftward by setting low = mid + 1.

   0    1    2    3    4    5    6    7
┌────┬────┬────┬────┬────┬────┬────┬────┐
│░ 3░│░ 9░│░14░│░21░│ 28 │ 33 │ 42 │ 55 │
└────┴────┴────┴────┴────┴────┴────┴────┘
                       ↑    ↑         ↑
                       L    M         R

Now the range is 4..7. Its middle is index 5, and arr[5] = 33, which is again less than 42. So we discard everything from mid leftward once more by setting low = mid + 1.

   0    1    2    3    4    5    6    7
┌────┬────┬────┬────┬────┬────┬────┬────┐
│░ 3░│░ 9░│░14░│░21░│░28░│░33░│ 42 │ 55 │
└────┴────┴────┴────┴────┴────┴────┴────┘
                                 ↑    ↑
                                L,M   R

Now the range is 6..7. Its middle is index 6, and arr[6] = 42 equals the target, so we return 6.

Three comparisons were enough to find the target in an array of eight. A linear scan, checking arr[0], arr[1], arr[2], and so on, would have needed seven comparisons to reach index 6. That gap only grows as the array gets larger, and we will count it exactly in a later section.