البحث الثنائي

Written Explanation

The idea

Take the sorted array {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} and search for 72. We keep a range of positions that might still contain the target, described by two indexes: low (the first position) and high (the last position). At the start the range is the whole array.

Repeat:

1. Find the middle position mid of the range.
2. If a[mid] equals the target, we are done: return mid.
3. If a[mid] is smaller than the target, the target can only be to the right, so set low = mid + 1.
4. If a[mid] is larger, the target can only be to the left, so set high = mid - 1.
5. If the range becomes empty (low > high), the target is not there: return -1.

Notice mid + 1 and mid - 1. We have already checked mid, so we exclude it from the new range. Writing just mid there can make the loop run forever.

Why it needs sorted data

Discarding half of the array is only safe if we know where the target would be. In a sorted array, "everything left of mid is smaller or equal, everything right is larger or equal", so a target bigger than a[mid] cannot be on the left. In an unsorted array that guarantee is gone: the half we throw away might hold the target, and the algorithm silently reports "not found" for a value that is there. The Java documentation for Arrays.binarySearch states the same requirement: the array must be sorted, and the result is undefined if it is not.

The code

static int binarySearch(int[] a, int target) {
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

Points to notice:

• The loop condition is low <= high, not low < high. With < a range of exactly one element (low == high) would be skipped and a target in it would be missed.
• The middle is computed as low + (high - low) / 2. The reason is next.
• With integer division (high - low) / 2 rounds down, so mid is always inside the range.

The middle and integer overflow

The obvious way to write the middle is (low + high) / 2. For small arrays it works. But recall that an int has a maximum value (about 2.1 billion), and adding past it wraps around to a negative number. If low and high are both very large, low + high can overflow, the "middle" becomes negative, and the program fails with an invalid index. This is a real bug that survived in widely used library code for years; Joshua Bloch described it on the Google Research blog, saying it can appear in arrays of about a billion elements or more.

You can see it with two big numbers:

int low = 1_500_000_000, high = 2_000_000_000;
System.out.println((low + high) / 2);
System.out.println(low + (high - low) / 2);

Output:

-397483648
1750000000

The first line is nonsense because the sum wrapped around. The second form subtracts first, so it never exceeds high, and gives the correct middle. We always use the safe form. You will not meet arrays this big in this course, but the habit costs nothing.

How many steps?

Each look halves the range. Starting with 1,000 elements the range shrinks roughly 1,000, 500, 250, 125, 62, 31, 15, 7, 3, 1. That is about 10 looks at most. In general, the number of looks is about how many times you can halve n before reaching 1. Doubling the array adds only one more look. Compared with linear search:

I counted a missing target in a sorted array of 1,000 elements with a counter and got 9 looks for the value below the smallest (the "always go left" path), which fits within the "at most about 10" bound.