* * * * *

                 Some notes on a binary search implementation

You would not believe how hard it was to write a binary search that returned
the correct index for a missing record in an array.

Even with _Programming Pearls_ [1] by Jon Bentley (reference book of the
day).

Binary search is a deceptively simple algorithm that is easy to get wrong (be
especially careful when searching empty arrays). And of the binary search
implementations I've seen, when they do return the index in the array, it's
to an element that's actually there, and some other value (like 0 or -1) if
the element isn't there. I've yet to see an implementation that returns an
index reguardless (plus an indication if the element was found or not).

So I spent several hours getting a binary search to return an index even if
the element wasn't found. Before looking at my solution [2] you should at
least try coding it (I should note that the code is pulled from the real-time
LaBrea data processing program I'm writing, which just enough changes to get
a single file to compile and with as little change to the source code as
possible, so some of the names may not make that much sense, but the logic
should be clear).

[1] http://www.amazon.com/exec/obidos/ASIN/0201657880/conmanlaborat-20
[2] gopher://gopher.conman.org/0Phlog:2006/01/15/bs.c

Email author at [email protected]

You are viewing proxied material from gopher.conman.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.