Say you want to find a specific song on your computer and for some reason the search bar isn't working (we'll spare you the Windows OS joke). All you have to work with is an alphabetically sorted list of every song you own.

For our sanity, you have two ways of finding the song. You could

1. start at the beginning of the list.
2. start in the middle of the list.

This decision might sound slightly less than important, but bear with us.

Let's say you start with the first element and move down the list. In the worst case, you'll have to go through the entire list before you realize that your song is last—literally, last—in the list. Or worse: you accidentally deleted it yesterday, so it isn't even there.

To be sure that you find the value, you have to go through every song, making the runtime of your search linear.

Unless you can cut out some steps.

If you start at the middle of the list, you cut the list in half with just one move. How? By comparing it to the middle song. If your song comes alphabetically before that middle song, go to the first half of the list—where every song also comes alphabetically before the song you checked. Go to the second half of the list if your song comes after the middle song.

You know what? Let's look at some songs.

If the song you're looking for is the classic, "This Shmoop is Your Shmoop," then you can compare it first to "My Shmoopy Valentine."

Since "My Shmoopy Valentine" comes before "This Shmoop is Your Shmoop," you'll move on to the middle of the larger half of the list: "Shmoop in the Mirror."

"This Shmoop is Your Shmoop comes after "Shmoop in the Mirror," so you can pick the song in the middle of the larger side of the list: "Shmooparazzi."

Same thing as before. When you move to the next possible element, "This Shmoop is Your Shmoop," you've found the song by while only checking half the songs in the list.

Ta da.

Instead of looking through every element in the list, you only had to check four to find the song. That's the beauty of logarithms: they let you do things in way fewer steps.

How many fewer? You only had to check half the list to find your song, making the number of steps log₂ 8 + 1. When searching, you won't need to check more than four songs until you literally double the number of songs in the list. Literally.

If you have a list with a million songs on it it'll take you

• 50,000 hours to hone your lip-syncing skills.
• 20 comparisons to find a song.

In sorting, we usually use base two and base three logs. Otherwise, we run the risk of causing a stack overflow—i.e. we try to use more memory than the computer can keep track of.

Bottom line: we can all agree that starting in the middle of the list—and splitting problems into sub-problems—will get us the answer much more easily than going through the entire list until our eyes glaze over.

Not bad for something invented to help sailors navigate at sea.