Binary Search bug in JDK

There was a famous bug which existed in JDK implementation of Binary Search

Randomly, I tried to reproduce the issue this weekend.

Here is the flawed implementation

public int search(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high) {
        int mid = (high + low) / 2;

        if(arr[mid] == target) {
            return mid;
        }
        else if (arr[mid] < target) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return -1;
}

If we execute this algorithm with following code:

BinarySearch binarySearch = new BinarySearch();
int[] newArr = new int[(int) Math.pow(2, 30) + 100];
System.out.println(binarySearch.search(newArr, (int) Math.pow(2, 30)));

We see the following exception

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1073741788
	at binarysearch.BinarySearch.search(BinarySearch.java:14)
	at binarysearch.BinarySearch.main(BinarySearch.java:31)

Process finished with exit code 1

The issue is in calculation of mid variable. The value high+low overflows the maximum range of int and ultimately results in negative value.

To fix this, we simply need to change the calculation of mid as follows:

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

This will give us the correct value of -1 which indicates that value doesn’t exist in the array.

Its amazing how simplest of bugs can remain undetected for years. This one remain undetected for nine years.