Sunday, January 15, 2006
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 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 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).