Guess the number.

Given the numbers 1 to 1000, what is the minimum number of guesses needed to find a specific number if you are given the hint ‘higher’ or ‘lower’ for each guess you make?

Ans:

Using Binary Search to find a number from 1 to 1,000

The approach most programmers would take is by starting your guess in the middle of the set of numbers, and then continuing to divide the set of numbers in half with each guess. This approach to guessing (or “searching” for the number) is known as a binary search to most software engineers, and it is also known as a half-interval search. Let’s go through an example of how the binary search would work so that you can further understand the approach to solving this problem.

An Example of using the binary search

So, let’s say the number you were trying to guess is a ‘1’. Then, you would start from the middle of 1,000 – which is 500. The person giving you hints would keep saying lower – and you would end up with something like this sequence of numbers to represent your guesses:

500, 250, 125, 63, 32, 16, 8, 4, 2, 1

Counting the number of guesses above would give you 10, which is our answer to the maximum number of guesses to find a number between 1 and 1000. In a binary search, if you take the log base 2 of the number of numbers (in this case, 1000), that would also give you the maximum number of guesses to find the correct number. So, if we take the log base 2 of 1,000 it would give us 9.965. Since you can’t possibly have a fraction of a guess, the result of log base 2 of 1000 should be rounded up to a whole number, which is 10, and the answer.