Problem of finding a number lying in a given range of values
Ask a friend to think of any number between 1 and 100. Let the number be called x. In how many chances can we find the answer x? The questions that can be used by us are whether the number x is less than or greater than or equal to some number. The answer is 7. How do we arrive at the solution? Guessing the answer is a different thing. But what is the logic behind such problems to get the correct answer.
This sounds really interesting and at the same time it is simple too. The answer depends on the number of values in the given range. Here the range is 1 to 100. The starting number in the range is called the lower limit and the ending number is called the upper limit. Here the lower limit is 1 and the upper limit is 100. The number of values is calculated using the formula upper limit – lower limit+1. In our example, the number of values is 100.
The secret in finding the answer is to express this number 100 in terms of the powers of the number 2. The power should be chosen such that it can accommodate the number of values. Let us see the case of our example, that is the number of values is 100. 2 raised to the power of 6 is 64 which is less than 100. 2 raised to the power of 7 is 128. 100 lies within 128. Hence 7 is the answer.
The procedure required to find the answer
The next question is how can one go about in finding the answer in 7 chances. Let us say the number thought of is 15.
Chance 1: Divide the range into two halves. That is now we have 1 to 50 and 51 to 100. We should ask the question "Is the number less than 51". "Yes" will be the answer from our friend. Hence, we can guess that the number lies between 1 to 50. Now, the range is reduced to half.
Chance 2: Again divide this range into two. The ranges we have now are 1 to 25 and 26 to 50. The second question should be like this. Is the number less than 26. The answer here will be yes.
Chance 3: Now, we can guess that the number lies between 1 to 25. The two ranges are 1 to 12 and 13 to 25. Note that the first range has 12 numbers and the second range has 13 numbers. This is purely an option. The ranges can also be 1 to 13 and 14 to 25. Let us now take the ranges as 1 to 12 and 13 to 25. The next question should be: Is the value less than 13. Now the answer will be: No.
Chance 4: Hence the range in which the answer lies is 13 to 25. The number of values in this range is 25-13+1=13. Note that the formula is upperlimit-lowerlimit+1. Dividing this into two will yield the two ranges, namely 13 to 18 with 6 values and 19 to 25 with 7 values. Now the question should be : Is the number less than 19. The answer will be yes. Hence the value lies between 13 and 18 having 5 numbers.
Chance 5: The two ranges got by dividing 13 to 18 into two halves are, 13 to 15 and 16 to 18. The question should be: Is the value less than 16 and the answer is yes. Hence the value lies between 13 to 15. Let us say we have the two divided ranges as one range with 13 and 14 and the second range with only 15.
Chance 6: Is the number less than 14 and the answer will be no. Hence the number is either 14 or 15.
Chance 7: Now the question should be Is the number less than 15. The answer will be no and hence the number thought of is 15 and hooray that is the right answer in 7 steps.
Note that the answer could have been arrived even at step 6. This is because we have expressed 100 as 2 raised to the power of 7 which can accommodate 128 values. But our range consists of only 100 numbers.
Now, let us take another example. What is the number of chances to find a value between 1 to 500. The answer is 9 because 2 raised to the power of 9 is 512 which is greater than 500. One can go ahead and challenge a friend to think of a number in a particular range and can find out the number the latter has thought of in a minimum number of chances using Binary Search technique.
The Binary search technique
The solution to questions of this kind is solved using the Binary search technique. The generalization of this technique is called Divide and Conquer method. The word binary stands for two. As the name goes, in this search method, the range is continuously divided into two halves till we arrive at the right answer. This method is used for numbers here. It can also be extended in finding a string in a given list of strings. The only condition required in binary search method is that the range of values should be in a sorted fashion. Otherwise this search technique cannot be applied.