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

And this too, will pass … the only question is when!

Back at The Hospital. The Younger is over definitely over his stomach flu, but the magnets are still stuck.

Normally on Sundays I run a D&D game for the family and The Kids were looking forward to playing this week, but frankly, I don't want to run a session at The Hospital. For one thing, I have a pile of reference material I use during a session and there isn't a good enough surface for me to use. And the smoke breaks (for both Spring and Wlofie smoke) will be longer (since they have to head outside The Hospital instead of just outside Casa New Jersey), leading to less actual gaming time.

Second, I'm still in a programming head space and don't want to loose being in The Zone.

Third, Spring fell asleep as soon as I got there, and Wlofie was home sleeping, and that's half the party. I'd rather not run a session with that many missing party members.

In an effort to get the magnets moving, The Younger is being forced to eat (not only by us, but through The Hospital staff) even though he complains of stomach pains.

I have this feeling that it's going to be a long hospital stay.

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

Squishing bugs

I've been simplifying the real-time LaBrea data processing program. One simplification: don't try to grow the arrays. If I'm trying to grow the arrays and I'm going to stop at some point anyway, why not just allocate as much as I'll ever use when the program starts? It gives you a definite upper bound (and one that can be set from the command line) and boy, does it simplify the code.

I also got the binary search routine working correctly after a few hours.

And I had to remind myself just how C's qsort() works, and make sure I know that (in my program at least) I'm getting pointers to pointers to structures, and not just pointers to structures (when I fixed that, I started getting correctly sorted arrays).

The only outstanding bug I have right now deals with adding a record after the array has been purged of old records. The problem is that I'm using an index from before the purge. I should be able to get this running on the LaBrea tarpit system in the next day or two.

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:, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

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-2023 by Sean Conner. All Rights Reserved.