Binary Search Midpoint Index Calculation

Question

So, the correct way to calculate mid in binary search is mid = low + ((high - low) / 2) to handle overflow errors.

My implementation uses unsigned 64-bit variables, and I never see a situation where my arrays become so large as to cause an overflow. Should I still use the above implementation or can I use mid = (low + high) / 2

What is the best practice here?

Answer 1

If there is no possibility of overflow, a safe way to calculate the midpoint is not technically necessary: ​​you can use an unsafe formula if you want. However, it is probably a good idea to keep it there anyway, in case your program changes in some way to violate your assumptions. I think adding one processor instruction to make your code promising is a big investment in the maintainability of your code.

Answer 2

Check this article Almost all binary searches and mutual conflicts are broken

Best practice (today)

Probably faster and perhaps clear: 6: int mid = (low + high) →> 1;

and after that:

In C and C ++ (where you do not have the operator →>), you can do this: 6: mid = ((unsigned int) low + (unsigned int) high)) → 1;

And in the end:

February 17, 2008 update: thanks to Antoine Trucks, senior member of the engineering staff at Nokia Finland Research Center, stating that the original proposed fix for C and C ++ (line 6) was not guaranteed to work according to the corresponding C99 standard (INTERNATIONAL STANDARD - ISO / IEC - 9899 - Second edition - 1999-12-01, 3.4.3.3), which states that if you add two signed values ​​and get an overflow, the result will be undefined. The old standards C, C89 / 90 and C ++ Standard are identical to C99 in this regard. Now that we have made this change, we know that the program is correct;)

The bottom line will always be the case when it will not work

Answer 3

The Don Knut method works fine through a bitmask without the possibility of overflow:

 return (low & high) + ((low ^ high) >> 1)