Binary Search Bug

FYI Here is an animation of a binary search which walks through the C code:

https://www.cs.usfca.edu/~galles/visualization/Search.html
[ note: numeric keypad input does not work, use the keyboard's top row ]
[ search: for the value found at index position 20 ]
[ controls at the bottom allow you to adjust animation speed and stepping ]

The following line of code was used for a long time in many standard programming libraries to find the middle point in a range of array indices for a binary search:

mid = (low + high) / 2; // find mid-point in a range of values

Your task is to identify and fix the bug in that calculation of mid.

d)What is potentially wrong with the(low + high) / 2 calculation to find the middle point? Under what conditions would the calculation go wrong?(7.5 points)
For a demonstration of the problem, runMidBugTest.exe found in this week's zip file.

e) REWRITE the code to prevent overflow (10 points)
from mid = (low + high) / 2;
to mid = ;

It must be assumed that mid,low, and high are all variablesof the same numeric data type; an arithmetic operation on twovariables of the same type always returns a value of that type. Agood programmer would clearly indicate, by casting and/or comments,if different data types – variables or constants – were beingmixed, and that is not the case here. A good programmer would bemindful of the possibility of overflow, and that is also not thecase here.

Given that mid is used in a binary search as anarray index, the data type will be int. Althoughthe size of an int varies depending on theplatform's C compiler, assume the minimum int sizeis sufficient for the application. The problem here is not aboutthe data type, its size, or bit width. The task is torewrite the arithmetic so that regardless of thevariables' data type, the calculation cannotoverflow.

Casting is not allowed because castingattempts to avoid the problem, i.e. bad programming andoverflow, rather than solve the problem. Even if a castedsolution works today, casting behaviour has changed over time andcould change on different platforms’ compilers so casting is notguaranteed to work tomorrow or even later today; it is also veryinefficient compared to a change in the arithmetic. Occam’s Razorapplies literally and metaphorically here.

Hint: The range of low to high values mayappear to fit within the range of an integer data type.
0-------------------------low--------------high---------INT_MAX

Instead of finding the average of (low + high) /2 as in the bug version,
0-------------------------low0------------------------------------------high
|                                  ^                                     |

first, find the middle point between low and high.
0-------------------------low--------------high---------INT_MAX  
                         low--------------high      
                         |        ^        |

Casting is computationally expensive and merely avoids the problem. Casting an intermediate result to a higher capacity data type will work reliably only if you cast from int to long long. That is thegood news. The bad news is you are avoiding the bug, not solving it. Your children will be faced with the same problem when a 64-bit sized int becomes the default. You do notwant them fixing this by casting to int128_tbecause then your grandchildren will inherit the problem. When will it end?

f) Describe the steps you used to develop and test your solution to the binary search bug. For the full 20 points ,what were the details of your process from problem analysis to solution implementation?