Wednesday, March 12, 2008

Binary Search in java by Joshua Bloch



1:     public static int binarySearch(int[] a, int key) {
2: int low = 0;
3: int high = a.length - 1;
4:
5: while (low <= high) {
6: int mid = (low + high) / 2;
7: int midVal = a[mid];
8:
9: if (midVal < key)
10: low = mid + 1
11: else if (midVal > key)
12: high = mid - 1;
13: else
14: return mid; // key found
15: }
16: return -(low + 1); // key not found.
17: }

The bug is in this line:   int mid =(low + high) / 2;

It
fails for large values of the int variables low and high. Specifically,
it fails if the sum of low and high is greater than the maximum
positive int value (pow(2 , 31) - 1). The sum overflows to a negative
value, and the value stays negative when divided by two. In C this
causes an array index out of bounds with unpredictable results. In
Java, it throws
ArrayIndexOutOfBoundsException.

So what's the best way to fix the bug? Here's one way:

    int mid = low + ((high - low) / 2);

Probably faster, and arguably as clear is:

  int mid = (low + high) >>> 1;