Binary Search

Miguel,
I am less impressed by that blog entry.

Let’s see… “In C this causes an array index out of bounds with unpredictable results.” Nope. In C it causes a signed integer overflow and hence unpredictable results. Consequently, casting the sum to unsigned will not fix it.

And if you are going to worry about overflow for one addition, why not
worry about overflow for the others? Line 10 and the subtraction on line 12 look safe, but
line 16 can overflow. That expression should be changed from
-(low + 1) to -low - 1. (I do not actually know if that is needed in Java, but in C it would be.)

Finally, the algorithm still does not work for sizes from 2^31 and up. To fix that, one would start working with unsigned quantities (thus solving the overflow problem as a side effect) and think of some other way of returning “not found”.

Comments are closed.