Skip to content
February 7, 2009 / Ben Chun

That Other Thing

Since I’ve had my coffee today, I feel like it’s worth mentioning the other side to yesterday’s sad story. There’s a thing, which I think is actually the same thing for most teachers, that makes this job worth doing. While it’s difficult to toss out an exact definition without wringing the life from it, perhaps an example will suffice.

Earlier this week, I was talking to my AP Computer Science class about searching. The setup is simple: we’ve got a big list of numbers and we’re trying to find out if a specific number is in the list. The most obvious and simplest way to accomplish this is to look at every number until you find what you’re looking for, or else get to the end of the list. Worst case, the number you wanted was the very last one and you had to look at every other number before you found it. I introduce a little vocabulary and notation, and ask them to think of ways to improve the performance. Crickets. So I add the twist that our list is now in order (even though we haven’t talked about sorting yet) and pretty quickly someone comes up with the basic idea of binary search: start in the middle and then you can decide if you need to look “higher” or “lower”. What I like about teaching this topic is that the concepts can be grasped immediately by my students, but this isn’t the sort of thing you’d just sit around and think about on your own.

As we’re analyzing the improvement in performance that we can get for a list of 10,000 numbers (and it turns out that using a binary search you need to check just 14 numbers, worst case, instead of all 10,000) I hear a boy who sits in the third row say quietly to himself, “That’s so cool.”


One Comment

Leave a Comment
  1. Steven Chun / Feb 8 2009 7:32 am

    So true. On the bike … the first turn out of the campground is the most important.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: