Overflow Bug in Binary Search

The first program which comes in our mind when we talk about Data Structures and Algorithms is Binary Search.

Binary search, also known as a logarithmic search is a search algorithm to find the position of a target value in a sorted array.

Photo by Anthony Martino on Unsplash

When a sorted array is given and we have to find the position of a value in the array the first approach can be linear search having a time complexity of O(n) but the better approach is no doubt binary search having a time complexity of O(logn).

Below is the Java implementation of iterative Binary Search,

Can you spot some bug in the above code?

No? Don’t worry, I’ll explain. The above program is correct there is nothing wrong in that unless the array is too big because if this happens then the value of l+r can go out of the range of Integer and that will result in an overflow.

If you are setting m=(l+r)/2, you have to be very careful. Unless you are using a language that does not overflow such as Python, l+r could overflow. One way to fix this is to use m=l+(r-l)/2 ​ instead so that the program will not fall under overflow bug.

If you fall into this subtle overflow bug, you are not alone. Even Jon Bentley’s own implementation of binary search had this overflow bug and remained undetected for over twenty years.

A study published in 1988 shows that the accurate code for it is found only in five out of twenty textbooks. Furthermore, Bentley’s own implementation of binary search, published in his 1986 book Programming Pearls, contained an overflow error that remained undetected for over twenty years. The Java programming language library implementation of binary search had the same overflow bug for more than nine years.

If we simply l+(r-l)/2 it will result in (l+r)/2 only but one should use the expression m=l+(r-l)/2 just to not fall in this overflow bug.

Proof of l+(r-l)/2 = (l+r)/2

Below is the correct Java implementation of iterative Binary Search that will not fall in overflow bug.

If you want to face this overflow bug, try the problem First Bad Version on LeetCode it is an implementation of Binary Search only. This problem has a test case that will cause an overflow bug if you will use m=(l+r)/2 .

If you will search for a Binary Search Program in Java on Google many reputed online portals that are highly followed by beginners are having inaccurate implementation that can cause overflow bug and it needs to be addressed.

Reading is good but reading with implementation is great!

Suggestions and critics about the article are most welcome.