Black Friday in Computer Science: 50% off!

This CS post is for non-Computer Science folks who are stuck on the couch ‘cause they ate too much and are tired from shopping.

So, in addition to the new smart TV you bought at Walmart for 50% off, did you know 50% off also applies to COMPUTER SCIENCE?

Get your CS nerd hat on, sit back, and enjoy a few moments.

One of the cool things we do in programming is something called sorting and searching. It is used behind the scenes in many of the activities YOU use daily. For example, when you search something on Amazon and then you can sort the results by price, quality, or ratings. When you go to the library and look up the new Jack Ryan book in the online search tool. Old timers will remember we used to use a card catalog in the library to look those up! Those same old timers also remember when we sent holiday cards, we had an address deck where we could scroll through our list of addresses. CD music lovers might sort their music collections by band name or album total. Teenagers scroll (i.e. search) through the music tracks on their phone looking for their favorite tune while studying. My brother has every Disney DVD movie EVER made in a huge bookcase in the playroom. I am sure he sorts it alphabetically.

For faster searching, the fact that the things we are searching are in order makes a difference, otherwise we are just going through randomly 1 by 1 asking repeatedly “is this it?” “No”, “is this it?” “No”, “is this it?” “No”, “is this it?” “No”, “is this it?” “No”. If they are in no particular order, we might find it on the first try, or it might take us until the last one. Right?

Let’s go one step further….if my brother is looking for the Frozen DVD, he can scan the movies and quickly zero in on that DVD. If he sees Cinderella, he knows Frozen is to the RIGHT. If he sees Maleficent, he knows it is to the LEFT.

Does that make sense?

Lets get even more efficient

Say my brother has 1000 DVD movies. And I challenged him to only look at 10 titles TOTAL, while searching(in other words, he can’t just scan across all 1000-–that would take forever), could he find the movie he is looking for quickly?

Well, yes he can. In fact, mathematically speaking, it should NEVER take more than 10 “looks”.

This is the idea behind binary searching. Each time we ask “is this it?”, we can eliminate a bunch of ones that we know are not it.

In fact, each time we can reduce by 50% ! OH YEAH!! It’s Black Friday in Nerdtown

Here is how it works (aka: the algorithm):

Within the collection of (pre-sorted) DVD movies, always find and look at the title in the exact middle. If the title is “less than” that middle title, then we know that all the titles to the RIGHT are not it, so we can “discard” them. If the title is “greater than” that middle title, then we know that all the titles to the LEFT are not it, so we can “discard” them. So each time we “look”, we can discard 50% of the titles. Repeat that process with the remaining DVDs, discarding 50% each time. You will find it quickly.

If you think about it…

1000(titles to start with) -> 500 -> 250 -> 125 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1(found it)

This algorithm will work for any quantity of DVDs, each time you “look”, just keep reducing by 50% until you are down to 1. Yes, it is possible you find it before the 1.

And this is not just true at Thanksgiving, it also works at Easter time.

And old timers will recognize the phone book in this example

Anyway, just a little CS to brighten you weekend, and to save you 50%!