DSA | Binary Search | Mistake which took around 9 years to surface

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky - Donald Knuth (Famous computer scientist)

As Donald Knuth says, it can get trickier with Binary Search; we'll cover Binary Search in a few articles. Today, our focus is primarily on revising the concept and learning about the mistake.

Binary Search is a search algorithm to find an element in a sorted array. It works on the principle of Divide and Conquer means we continue to divide our array into halves, and select the relevant half. Then again try finding the element in that half until we find the element or reach a point where we know the element does not exist in the array.

Time Complexity is O(logn). Space Complexity is O(1) for iterative implementation and O(logn) for recursive implementation.

Let's write an iterative implementation for now and then talk about issue.

The function returns the index of the element found else returns -1 if the element does not exist in the array.

int binarySearch (int[] arr, int element) {
	int low = 0;
	int high = arr.length - 1;
	 
	while (low <= high) {
		int mid = (low + high) / 2;

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

The above function will work fine but there is a probability of overflow when an element is somewhere in the right and we keep on looking for the element and reach a point where low and high become too big that their sum goes out of range of int which has upper bound of 2^31-1. (Multiple languages may have different upper bounds, here we took the example of Java, but the possibility of breaching the upper bound still persists).

Let's assume we've got an array of size 2^31 - 1 with elements in increasing order and the element to be searched is the second last element which is 2^31 - 2.

[1, 2, 3, 4, 5, 6, 7 ...........2^31 - 3, 2^31 - 2, 2^31 - 1]

In the first iteration of the loop, mid will be computed as -

low = 0, high = 2^31 - 1
mid = (0 + 2^31 - 1) / 2 which equals 2^31/2

Since the element is in the right half of the array, in the next iteration, mid will be computed as -

low = 2^31/2 + 1, high = 2^31 - 1
mid = ((2^31/2 + 1) + (2^31 - 1)) / 2 

The new value of mid will cause overflow as the sum would exceed 2^31. In the case of Java, the sum would be returned as a negative value, and thus would cause an ArrayIndexOutOfBounds exception.

As per an article written in 2006 by Joshua Bloch here (https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html) - "the version of binary search that I wrote for the JDK contained the same bug. It was reported to Sun recently when it broke someone's program, after lying in wait for nine years or so."

I hope, you got the mistake, the more interesting part is how to solve this about which we'll talk in upcoming articles!

Do stay connected on LinkedIn, Facebook, Twitter, YouTube, or wherever you feel comfortable. See you soon!

Till then, Keep Learning, Happy Tech Learnings!