"Guess the Number" and Binary Searching! 🔍

Putting some words and formality to an approach for finding things that you and I have probably been using for quite some time!

Hi everybody - have you ever played the Guess the Number game? If you haven’t, take a few moments and give it a try from this link and start entering some numbers:

If you haven’t figured out the rules from playing the game a few times, here they are:

1. The game is typically played with two or more players

2. One player selects a number between a predetermined range (e.g. 1-100), and keeps it a secret from the other players

3. The other players take turns guessing what the secret number is

4. After each guess, the player who selected the secret number will respond with a hint such as higher or lower

5. Players continue taking turns until someone correctly guesses the secret number

Our version of the game here is played between you and the computer, and you will always play the role of number guesser. The computer will pick a random number between 0 and 100.

When you start the game, you will pick a number first. This first guess will act as an anchor that will guide your next guess based on what the computer tells you. If the computer’s chosen number is higher, you’ll guess a higher number. If the computer’s chosen number is lower, you’ll guess a lower number. With each guess, you’ll get more higher or lower guidance from the computer. Eventually, you’ll hone in on the correct number and make a successful guess.

Binary Searching

There is a more formal name for the approach we used to find the number our computer guessed. It is known as a binary search. To learn all about binary search, check out my in-depth tutorial here. For a bite-sized overview, do read on!

What makes binary search effective is that it eliminates many unnecessary paths (usually eliminates by half) as it works towards finding the item we told it to find!

It's a divide-and-discard algorithm whose techniques we use in real life all the time. We used a less strict version of binary search when playing our Guess the Number game. When a guess was too large, we discarded all numbers that would have been larger. When a guess was too small, we discarded all numbers that were smaller.

For another example, whenever we look up a word in a physical dictionary, we use binary search again:

We know that all of the letters in the dictionary are alphabetically sorted. We can divide and discard our way toward finding the word we are looking for easily!

Conclusion

Connecting the dots a bit, this explanation of binary search is part of my upcoming book and tutorial series on data structures & algorithms. Periodically, I’ll share some of my latest content with all of you as shown in this newsletter article today.

Speaking of sharing, please feel free to like or retweet my tweet on this topic:

🍊 KIRUPA @kirupa

Linear search is great and all, but have you checked out binary search and its blazing fast O(log n)-ness? 🚀 #webdev #Algorithms #developer kirupa.com/data_structure…

kirupa.comFaster Searching with Binary SearchSearch items at a blazing log(n) speed by learning how binary search works, how it can be implemented, its performance details, and more.

Lastly, before I forget, there is more fun and learning to be had. The Guess the Number game you played is part of a larger coding exercise where you get to try your hand at creating the whole example and sharing your result with others. There is a cool badge you can earn.

As always, thank you for reading till the end and having my content take up valuable space in your inbox and in your life. See you all next time and feel free to reach out to me on Twitter or on the forums.

Cheers,
Kirupa 😇