C in Xcode Given the numbers 1 to 1000 what is the minimum n

C++ in Xcode

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?

Read the question carefully and you’ll note that the question asks for the ‘minimum’ number of guesses. Think about it – someone can guess the right question on their first try right?

So, the answer here would be ‘1’, since it would take only one correct guess to find a specific number.

Finding the maximum number of guesses

But, what if we wanted to find the maximum number of guesses?

Solution

Given an interval [a,b], your guess should be the middle element i.e. (a+b)2(a+b)2 at each step. If your guess is right, then great! Otherwise, you should adjust your bounds of your current interval. If that specific number is \"higher\", your new interval will be [(a+b)2+1,b][(a+b)2+1,b]. Similarly if it is \"lower\" then your new interval will be [a,(a+b)21][a,(a+b)21]. You will keep guessing until the lower bound is greater than the upper bound, in other words, until your interval collapses. If you still couldn\'t find the solution, then the person who asked you this question is cheating!

For instance, your initial interval is [1,1000] and your first guess will be 500. Then assume you are given the hint \"higher\", then your new interval will be [501, 1000] and your next guess should be 750. Similarly if the hint was \"lower\" than your interval would be [1,499] and your next guess would be 250.

This guarantees that in the worst case you are able to find the solution in log2nlog2n steps where nn is the length of your initial interval. In our example you need maximum of log2100010log2100010 guesses to find the correct answer. In the logarithm base 2 comes from the \"division\" we make. At each step, we eliminate half of the possibilities.

This is a simple binary search question.
Like you first guess will be is the number is less than 500.
If yes: Is that is less than 250
If yes: is this is less than 375 …..
If No:Is it less than 750 ….

So in worst case you questions will be log₂(1000).