The Boston Diaries

The ongoing saga of a programmer who doesn't live in Boston, nor does he even like Boston, but yet named his weblog/journal “The Boston Diaries.”

Go figure.

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).

Obligatory Picture

[It's the most wonderful time of the year!]

Obligatory Contact Info

Obligatory Feeds

Obligatory Links

Obligatory Miscellaneous

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: http://boston.conman.org/, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

http://boston.conman.org/2000/08/01

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.

Copyright © 1999-2021 by Sean Conner. All Rights Reserved.