If a person has a number between 1 and 100 in mind, you can always figure out what this number is by asking no more than 7 questions “Is your number the same, smaller than or equal to x?” where x is to be determined. The trick is to a binary search so that at least half of the all possibilities are eliminated after each question For example, if the secret number is 59, the following could take place (you may want to use –1 for less than, 0 for equal to, and 1 for larger than)
Is your number equal to, less than, or larger than 50: 1
Is your number equal to, less than, or larger than 75: -1
Is your number equal to, less than, or larger than 62: -1
Is your number equal to, less than, or larger than 56: 1
Is your number equal to, less than, or larger than 59: 0
Write a C program that plays this game. Make sure that you use this binary search:
The indices for the objects to be searched are low, low+1, low+2, ..., high (in our case, they are initially 1, 2, ..., 100). The middle is at m = (low+high)/2 (note that this is an integer division. If m is not the answer, then if the number is less than m, then we need to search between low and m-1. Otherwise, m+1 and high.
I am having major difficulties making this computer program for school. I was hoping someone would be able to guide me in the right direction with this post.