Overflow Bug in Binary Search

Sourabh Gupta
May 3, 2020 · 3 min read

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.

Image for post
Image for post
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,

BinarySearchOne.java

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.

Image for post
Image for post
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.

BinarySearchTwo.java

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.

Sourabh Gupta

Written by

Full-stack Developer | UX/UI | Never ending thirst to learn.

The Startup

Medium's largest active publication, followed by +756K people. Follow to join our community.

Sourabh Gupta

Written by

Full-stack Developer | UX/UI | Never ending thirst to learn.

The Startup

Medium's largest active publication, followed by +756K people. Follow to join our community.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store