Bug and fix for Bentley's Binary Search code

#1

The bug is that M = (L + U) / 2; could lead to Integer overflow

The fix suggest using M = L + (U - L) / 2;

I found it much more intuitive to use M = L / 2 + U / 2; as the fix which is mathematically equivalent to M = L + (U - L) / 2: (see the derivation below).

The derivation:
M = L + (U - L) / 2;
M = L + U / 2 - L / 2;
M = L - L / 2 + U / 2;
M = L / 2 + U / 2;

So is there any specific reason to write M = L + (U - L) / 2; as the fix?

0 Likes
#2

Is it because the integer rounding after dividing twice could lead to different result than dividing once?

0 Likes
#3

Hi @yhzs88,

Yes, the rounding twice will result into incorrect result. For example, if L = 3 and U = 5, the one in the book gives you M = 4 but yours gives M = 3.

0 Likes