top of page
  • LinkedIn
  • Facebook
  • YouTube
  • Twitter
  • Instagram
  • Pinterest
  • Tumblr
  • Vkontakte

Middle Value Overflow In Binary Search Explained

Updated: Jun 3, 2022


Introduction


Binary search is one of the most popular searching algorithms in computer science. If you know the binary search algorithm already, you may have come across a section in this algorithm where you try to find the middle element in the array (or search space to be more precise).


Note: It is important to note that this overflow error is not limited to binary search alone. It applies all algorithms that have a similar use case for getting middle element.


A very basic implementation of binary search uses the below formula for calculating the middle element:


mid = (left + right)/2


where left and right represent the indexes of the first and the last element in the current search space. A first glance on this basic formula for middle index calculation, everything looks correct and in fact the formula works perfectly fine for most cases, until you start noticing that your algorithm is producing an unexpected output (or even error in some programming languages) for some specific values of input.


The reason for this unexpected failure may not be fairly obvious at first. It occurs due to a hidden flaw in this seemingly straight forward formula for middle index calculation. At the root, the reason for this failure is something called an overflow condition in computer programming.


Basic Formula: Overflow Explained


Why does the above basic formula to calculate middle value result in an overflow?


The max value an integer (data type in a programming language) can hold can vary from machine to machine, OS to OS or even based on the programming language itself. For the sake of our example and for easier understanding, assume this value, lets call it MAX_INT, is 100.


Consider we are given an array with n=90 elements and our target element is the last element in the array, at 89th index. Binary search algorithm starts with left=0 and right=89. Since the target element is the last element in the array our search space keeps shifting to the right (refer binary search for more details). So (left,right) will be (0,89) for the first iteration and (45,89) for the second iteration. Now using our basic formula to calculate mid value for the first iteration, we get mid = (0+89)/2 = 45, for the second iteration, mid = (45 + 89), but (45 + 89) exceeds our MAX_INT value of 100 resulting in overflow. Thus our program might produce some unexpected output or result in an error depending on the programming language we are using. This is how the basic formula for middle element calculation fails. Also note that, generally the MAX_INT will be much higher, we assumed it as 100 just for the ease of understanding.