Binary Search: Halve It Every Time

The guessing game

I think of a number from 1 to 100. You guess 50. I say “higher”. Now you know it's 51–100 – half the numbers are gone with one guess. Keep guessing the middle and you'll always win in at most 7 guesses.

Binary search does this on a sorted array. Keep two bounds, lo and hi, and look at the middle:

public class Main {
    static int binarySearch(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            System.out.println("  look at index " + mid + " (" + a[mid] + ")");
            if (a[mid] == target) return mid;
            if (a[mid] < target) lo = mid + 1;    // target is on the right
            else hi = mid - 1;                     // target is on the left
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] rolls = {3, 8, 12, 19, 25, 31, 40, 47, 52, 66};
        System.out.println("find 47:");
        System.out.println("index " + binarySearch(rolls, 47));
        System.out.println("find 20:");
        System.out.println("index " + binarySearch(rolls, 20));
    }
}

Output

find 47:
  look at index 4 (25)
  look at index 7 (47)
index 7
find 20:
  look at index 4 (25)
  look at index 1 (8)
  look at index 2 (12)
  look at index 3 (19)
index -1

Tip: lo + (hi - lo) / 2 is the same as (lo + hi) / 2 but can't overflow when lo and hi are huge.

Common mistake: Using binary search on an unsorted array. It doesn't crash – it just gives wrong answers. Sort first (Arrays.sort) or use linear search.

Java's built-in

Arrays.binarySearch(a, x) does the same job. If x is missing it returns a negative number.