DEV Community

JAY
JAY

Posted on

Binary Search: The Secret Behind the Number Guessing Game

#beginners #algorithms

There's a number guessing game: I'll think of a secret number between 1 and 100, and you try to guess it. After each guess, I'll tell you if your guess is too high or too low. Your goal is to find the secret number in as few guesses as possible. There's a website where you can test how many guesses you need: Guess Number Game.

What if I told you there's a clever strategy that can find any number between 1 and 100 in just 7 guesses or less? That's right - no matter what number you're trying to find, you'll never need more than 7 attempts. This powerful technique is called Binary Search, and it's one of the most elegant algorithms in computer science. Let me show you how it works!

Binary Search in Action

Let's say we're playing the number guessing game with numbers 1-100, and the secret number is 73. Here's how binary search would solve it:

  1. First guess: 50 (too low)
    • We know the number must be between 51 and 100
  2. Second guess: 75 (too high)
    • Now we know it's between 51 and 74
  3. Third guess: 62 (too low)
    • The number must be between 63 and 74
  4. Fourth guess: 68 (too low)
    • We narrow it down to 69-74
  5. Fifth guess: 71 (too low)
    • The number is between 72 and 74
  6. Sixth guess: 73 (found it!)

In just 6 guesses, we found the number! That's much better than checking every number from 1 to 73. The secret? We're always cutting our search space in half with each guess. This is why it's called "binary" search - we're constantly dividing our possibilities into two parts.

Image description

Comparing Different Guessing Strategies

Let's analyze three different approaches to the number guessing game and see how they stack up against each other:

1. Sequential Guessing (Linear Search)

  • Strategy: Guess numbers in order (1, 2, 3, 4...)
  • Worst case: 100 guesses (if the number is 100)
  • Average case: Let's calculate this!
    • If the number is 1, we need 1 guess
    • If the number is 2, we need 2 guesses
    • If the number is 3, we need 3 guesses
    • And so on...
    • The average is (1 + 2 + 3 + ... + 100) ÷ 100 = 50.5 guesses
  • Pros: Simple to understand and implement
  • Cons: Extremely inefficient for large ranges

2. Random Guessing

  • Strategy: Pick numbers randomly within the range
  • Worst case: 99 guesses
    • In the worst case, we might keep guessing numbers we've already tried
    • For example, if the number is 100, we might keep guessing numbers between 1-99
    • Only when we've tried all other numbers will we finally guess 100
  • Average case: The mathematical formula is quite complex, but here's the result:
    • Through mathematical analysis and simulation, for n=100, the expected number of guesses is approximately 8.05
    • This is much better than the worst case, but still not as efficient as binary search
  • Pros: No pattern to follow
  • Cons:
    • Highly unpredictable
    • Can take many more guesses than necessary
    • Expected performance is worse than binary search

3. Binary Search

  • Strategy: Always guess the middle number of the remaining range
  • Worst case: 7 guesses (for numbers 1-100)
  • Average case: Let's break this down!
    • With each guess, we eliminate half of the remaining numbers
    • After 1 guess: 50 numbers left
    • After 2 guesses: 25 numbers left
    • After 3 guesses: 12-13 numbers left
    • After 4 guesses: 6-7 numbers left
    • After 5 guesses: 3-4 numbers left
    • After 6 guesses: 1-2 numbers left
    • Most numbers will be found in 6 guesses
    • Only a few numbers at the edges might need 7 guesses
    • That's why the average is around 6 guesses
  • Pros:
    • Extremely efficient
    • Predictable performance
    • Guaranteed to find the number
  • Cons: Requires keeping track of the range

Why Binary Search Wins

The binary search strategy is clearly superior because:

  1. It has a guaranteed maximum number of guesses (7 for 1-100)
  2. It's deterministic - you always know exactly how many guesses you'll need
  3. It's much faster than both sequential and random guessing
  4. The efficiency scales well with larger ranges (for 1-1000, it would take at most 10 guesses)

This is why binary search is one of the most fundamental algorithms in computer science - it's incredibly efficient at finding items in sorted data. The same principles we use in the number guessing game can be applied to searching through databases, finding files, or solving many other real-world problems.

Top comments (0)