|
Binary search of an array is a notorious example of a simple algorithm
which is hard to get exactly right. The variant we're using is nice
because it automatically computes the correct insertion point when a
key doesn't exist, but runs into one of the portability corner cases
of signed integer arithemtic in C. Rather than leave a landmine
waiting to explode if somebody builds this code on a platform where
(-1 >> 1) != -1, we test for the corner case explictly and accept the
miniscule performance hit (which will be lost in other noise anyway).
|
