Binary Search: so simple your child has done it

Photo by Jerry Wang on Unsplash

Binary Search: so simple your child has done it

An oversimplification of a coding algorithm

I wasn't a Computer Science major. That is to say, I'm not the kind of person who would probably have had algorithms on the brain. When I got to Coding Boot Camp we covered Algorithms, Data Structures, and the like. I did, however, find algorithms interesting. The word 'algorithms' alone was enough to make me feel anxious at first (as many multisyllabic words do). They turned out to be a great way to learn about how to approach the code I would later write.

What's this thing do?

I realized one search algorithm is something we innately do as children: Binary Search. "Binary" means that it's referring to two things. A binary question would be one where there are only two reasonable responses, say a "yes" or "no" for instance. So Binary Search will have something to do with two states (while you haven't found what you're looking for): before or after.

My four-year-old has even demonstrated how intuitive this algorithm is. My daughter was looking for a certain part of a book she likes. So here's what I saw my four-year-old do:

Open the storybook to an arbitrary place
    while she has not found what she's looking for:
        Look at the pictures to see where she was in the story
           if it's before that, look to the left in the book
           else look to the right

Not too complicated. You've probably done this every time you pick up a real dictionary or phone book. That's basically all Binary Search is, except for two requirements:

  1. The items you are searching through have to be sorted.
  2. You always look at the middle of whatever is left in your search, not an arbitrary value.

Is it worth it?

That's what the process basically looks like. Now, let's play a game. I'm going to pick a number between 1 and 1,000. It's going to be 1,000. Let's try it as a sequential search, that's where you start at the beginning and check each one in order. In the worst-case scenario, you will have to guess every number to find it. That's maybe a thousand guesses and a loss in the faith of everyone that you have mind-reading abilities. With that same game, it would take something like 10 moves to find what you're looking for with Binary Search. Ten guesses out of a thousand options are far better, efficiency-wise, than guessing each number until you get it.

Put a different way: How would you rather look up words in the dictionary? One word at a time? Or is it faster to open the book and see if you found it the first time and adjust your search? Binary Search is something you already do a version of.