Category Archives: Binary search

Buffy: Season 1, revisited

Those of you who have become regular readers of The Reinvigorated Programmer but who don’t watch Joss Whedon’s show Buffy the Vampire Slayer will probably be inclined to skip over this article. Don’t do that! I hope to show you that Buffy has depths that you’re probably not aware of, and maybe to introduce you to a TV programme that you’ll not only enjoy over the next few months, but also add to your cultural tapestry.  Buffy is very, very good, and I missed it for a long while because I thought it sounded dumb and fluffy and insubstantial.  My bad.  Don’t make the same mistake I did.

Continue reading

Writing correct code, part 3: preconditions and postconditions (binary search part 4c)

Having dealt (briefly and informally) with invariants and bound functions in the two previous installments of this series, it’s time to look at preconditions and postconditions.  These will likely be familiar to most of you, even those who’d not heard of invariants before, because these days they are known by the trendy, XP-friendly name design by contract.  (OK, it’s not quite the same thing; but they’re closely related concepts.)

Continue reading

Writing correct code, part 2: bound functions (binary search part 4b)

Following on from yesterday’s article on invariants, this time we’ll talk about a second tool in the kit for thinking about code.  This one will be much shorter, because the Concept Of The Day is so simple.  It gets talked about even less than invariants, but let’s change that!

(Oh, and today is vegetarian-friendly Cheese Day at The Reinvigorated Programmer, though it still may not be much use to the vegans among you.)

Continue reading

Writing correct code, part 1: invariants (binary search part 4a)

I’m struggling with my article numbering now :-)

Regular readers will have noticed that I am running a whole bunch of series in parallel on this blog: one reviewing programming books, one on the issue of simplicity in programming, one reviewing Series 5 of Doctor Who, a related one on Russell T. Davies’s contributions, and one on learning Lisp.  To my huge surprise, what started out as a review of Jon Bentley’s book Programming Pearls [amazon.com, amazon.co.uk] has led through a sequence of digressions and become a series of its own on binary search.  This is part 4 of that series: when I’ve finished part 4, I will — at last! — progress to the actual review.  But since part 4 is about the distinctly non-trivial subject of writing correct code, it will itself have to be composed of multiple sub-parts.  So this article on invariants is both part 1 of the new writing-correct-code series and part 4a of the binary-search series.  Hope that’s clear.

A few people have complained about the sushi pictures on this blog, so before I plough into the article proper, here is something completely different.

Continue reading

Testing is not a substitute for thinking (binary search part 3)

The contributions to the original binary search thread continue to trickle in, and now stand at an astonishing tally of 679 comments, most of them containing code.  Thanks once more to all of you who’ve attempted this challenge, and to everyone who’s commented.

In one of the more interesting comments, Darius Bacon tested a sample of 20 of the Python submissions, and found that exactly 10% of them both passed the functional test and appeared to run in O(log n) time — which of course is exactly in line with Jon Bentley’s original statistic, that 10% of the professional programmers he’d examined were able to write correct binary search code (albeit under rather different conditions).  It subsequently became apparent, though, that Darius’s testing code was overly strict, and that a further two of the sampled routines did run correctly (though not necessarily in O(log n) time).  Still — it’s a surprisingly low hit-rate, especially when you bear in mind that, contrary to the rules, many of the programmers did use testing to help them develop the code. (You should read the second linked comment, as it has plenty of other interesting observations, too.)

[Update, an hour or two later: as Darius Bacon points out in a comment below, I misinterpreted his results.  Once the testing code had been fixed, his sample of 21 routines found 9 that passed all test, of which 6 were O(log n).]

Continue reading

Common bugs and why exercises matter (binary search part 2)

Many, many thanks to all of you who have contributed to the astonishing response to the previous article on the difficulty of getting binary search right.  I’ve never seen anything like this: in just over 24 hours since I posted the article, 541 comments have been posted, and they’re still rolling in.  (That number is a bit inflated by people re-posting the same code-samples multiple times after seeing WordPress mangle their source, but even taking that into account it still amazes me.)

You guys rule.  Seriously.

I have a lot to say in response to it all.  Read on …

Continue reading

Are you one of the 10% of programmers who can write a binary search?

There are some programming books that I’ve read from cover to cover repeatedly; there are others that I have dipped into many times, reading a chapter or so at a time.  Jon Bentley’s 1986 classic Programming Pearls is a rare case where both of these are true, as the scuffs at the bottom of my copy’s cover attest:

(I have the First Edition [amazon.comamazon.co.uk], so that’s what I scanned for the cover image above, but it would probably make more sense to get the newer and cheaper Second Edition [amazon.comamazon.co.uk] which apparently has three additional chapters.)

Continue reading