Number Guessing Game

How it works

The game picks a random number within a configurable range. You enter a guess and get immediate feedback: "too high", "too low", or "correct". Proximity feedback (hot/cold/warm) gives you a sense of how close you are, even beyond just direction.

The binary search connection

This game is binary search in disguise. The optimal strategy — always guess the midpoint of the remaining range — is exactly how binary search works in programming. For a 1-100 range, the maximum guesses needed using this strategy is 7 (since log₂(100) ≈ 6.6). That number comes from asking: how many times can you cut 100 in half before you are left with a range of exactly one number? The answer is the base-2 logarithm of the range size, rounded up.

To understand why the midpoint is always optimal, consider what each guess accomplishes. When you guess any value x and receive "too high", you learn that the target lies in the lower portion of your current range. When you receive "too low", you learn the target lies in the upper portion. The question is: which value of x eliminates the most possibilities regardless of the outcome?

If your current range has n numbers in it, guessing the midpoint splits it into two halves of size n/2 each. No matter what the answer comes back as — "too high" or "too low" — you are left with at most n/2 candidates. Any other guess creates an uneven split: guessing a value near the top of the range means a "too high" response leaves only a small number of candidates, but a "too low" response leaves most of the range intact. The midpoint is the only guess that guarantees the worst case is as good as it can possibly be.

The log₂(N) math explained

The maximum number of guesses you need with perfect binary search strategy is the ceiling of log₂(N), where N is the size of your range. Log₂(N) answers the question: to what power must you raise 2 in order to get N? For N = 100: 2⁶ = 64 and 2⁷ = 128, so log₂(100) falls between 6 and 7. Rounding up gives 7, which means 7 guesses are always enough.

You can compute it intuitively by counting halvings. Start with 100. Half of 100 is 50 (1 guess). Half of 50 is 25 (2). Half of 25 is 12 or 13 (3). Half of 12 is 6 (4). Half of 6 is 3 (5). Half of 3 is 1 or 2 (6). With a range of 1 or 2 numbers, one final guess resolves it (7). Seven halvings bring any 1-100 range down to a single candidate.

Full worked example: range 1-100, target 73

The table above shows a six-guess solution. Here is the reasoning behind each midpoint choice, spelled out step by step, to make the strategy concrete.

Guess 1 — midpoint of [1, 100]: (1 + 100) ÷ 2 = 50.5, round down to 50. Submit 50. Response: too low. The target is in [51, 100]. Range size reduced from 100 to 50.

Guess 2 — midpoint of [51, 100]: (51 + 100) ÷ 2 = 75.5, round down to 75. Submit 75. Response: too high. The target is in [51, 74]. Range size reduced from 50 to 24.

Guess 3 — midpoint of [51, 74]: (51 + 74) ÷ 2 = 62.5, round down to 62. Submit 62. Response: too low. The target is in [63, 74]. Range size reduced from 24 to 12.

Guess 4 — midpoint of [63, 74]: (63 + 74) ÷ 2 = 68.5, round down to 68. Submit 68. Response: too low. The target is in [69, 74]. Range size reduced from 12 to 6.

Guess 5 — midpoint of [69, 74]: (69 + 74) ÷ 2 = 71.5, round down to 71. Submit 71. Response: too low. The target is in [72, 74]. Range size reduced from 6 to 3.

Guess 6 — midpoint of [72, 74]: (72 + 74) ÷ 2 = 73. Submit 73. Response: correct! Found in 6 guesses, one fewer than the theoretical maximum of 7.

Notice that each guess was computed purely from the current low and high boundaries. You do not need to remember previous guesses — only the current valid range. This simplicity is part of what makes the strategy easy to execute under pressure.

Optimal guessing strategies

The number guessing game is a practical demonstration of search algorithms. There are three main strategies, with dramatically different expected attempt counts.

Why random and sequential guessing are so much worse

Sequential guessing — trying 1, then 2, then 3, and so on — will always find the answer eventually, but on average it takes 50 guesses for a 1-100 range. If the hidden number is 99, you need 99 guesses. If it is 1, you need only 1. The expected value across all equally likely targets is (1 + 100) ÷ 2 = 50.5. In the worst case you need the full 100 guesses. Compare that to binary search's worst case of 7. The difference is not incremental — it is the difference between a practical strategy and an impractical one.

Random guessing sounds like it might do better than sequential because you could get lucky and hit the number early. But on average, random guessing without repeating previous answers has the same expected count as sequential: about 50 for a 1-100 range. The variance is higher — sometimes you guess correctly on the third try, sometimes it takes 95 — but the mean is roughly the same. More importantly, random guessing without tracking which numbers you have already tried can lead to re-guessing numbers, which is strictly worse than either sequential or binary search.

The deeper lesson is about the value of information. Every guess in binary search is chosen specifically to maximize the information gained from the response. The midpoint is the unique guess that makes "too high" and "too low" equally informative. Any deviation from the midpoint creates a situation where one response gives you more information and the other gives you less, and the less informative response sets back your progress. Binary search is optimal precisely because it refuses to bet on a particular outcome.

Where binary search appears in real computing

The same principle you use to play this game efficiently is deployed throughout software systems. Understanding it in the concrete context of a number-guessing puzzle makes the abstract computer science concept immediately intuitive.

Sorted array lookup: databases and programming language standard libraries use binary search to find a value in a sorted list. Python's bisect module, Java's Arrays.binarySearch, and C++'s std::lower_bound all implement this algorithm. Searching one billion sorted records takes at most 30 comparisons with binary search (log₂(1,000,000,000) ≈ 30), whereas sequential search could require all billion comparisons in the worst case.

Git bisect: the Git version control system provides a git bisect command that uses binary search to find the specific commit that introduced a bug. You tell Git which commit is good and which is bad, and it checks out the midpoint commit for you to test. After you mark it good or bad, it halves the range again. A codebase with 1024 commits can be bisected in at most 10 steps.

IP address routing: network routers maintain routing tables indexed by IP prefix. Looking up which route to use for a given destination address is a binary search problem on the sorted prefix space. The logarithmic lookup time is what makes routing scalable as the internet grows.

Dictionary and spell-check lookups:before hash tables became ubiquitous, dictionaries in software were stored as sorted arrays and looked up with binary search. Even today, when memory is constrained and a hash table's overhead is not acceptable, sorted arrays with binary search are the standard alternative.

Debugging performance issues:engineers often use a manual form of binary search when diagnosing slow systems. If a system with 100 steps is running slowly, you time it at the midpoint — step 50. If the slowdown has already occurred by step 50, the problem is in steps 1-50. If not, it is in steps 51-100. Repeat until the problem narrows to a single step. This informal bisection is faster than any other debugging strategy when the problem space is large and each test is expensive.

The number guessing game distills all of these use cases into their most fundamental form. Mastering the strategy here — always pick the midpoint, always track your valid range — means you have already internalized one of the most important algorithms in computer science. When you next encounter a sorted list, a version history, or any search problem where comparisons give directional feedback, you will recognize the same structure and know exactly what to do.

Frequently Asked Questions