How to write a binary algorithm for C/C++

Question

I am having trouble to write the binary algorithm in C/C++.
My question is like that:

Apply binary algorithm to search for a number from 1 to 100 in a number guessing game.
The user will respond with 'y' for a correct guess, 'h' if the guess is too high or 'l' if the guess is too low.

I don't have any idea to apply it. Can someone just give me an example of the code.

• Nick Dandoulakis: I think you mean a divide and conquer algorithm
• Donnie DeBoer: What aspect of the problem are you having trouble with?
• Vijay: beginners do mistakes and they dont deserve one down.i am making it +1
• qrdl: @benjamin Nothing to do with mistakes. People should at least try to solve the problem before asking for help. So -1
• Andreas Brinck: There's no rule on SO that states that people have to try and solve their problems before asking for help.

Answer 1

Detailed instructions here plus various implementations.

int low = 1;
int high = 100;
while (low <= high) {
 int mid = (low + high) / 2;
 char answer = evaluateGuess(mid); //return l, h or y;
 if ('y'==answer) {
 return mid;
 }
 if ('l' == answer) {
 low = mid + 1;
 } else {
 high = mid - 1;
 }
}
// If you get here the human player lied and the answer wasn't in [1..100] 

Answer 2

I assume you mean binary search. Wikipedia has loads of information. You also haven't specified if you can use the stl.

The basic pseudo code is

 min := 1;
 max := N; {array size: var A : array [1..N] of integer}
 repeat
 mid := (min + max) div 2;
 if x > A[mid] then
 min := mid + 1
 else 
 max := mid - 1;
 until (A[mid] = x) or (min > max);

So in you case, min is 0, max is 100, where could alter the above algorithm to that it supports user input. All that needs to happen is rather than the comparison checks on an array, you just need to check user input.

 min := 1;
 max := 100;
 repeat
 mid := (min + max) div 2;
 print mid;
 c := getChar();
 if c == 'h' then
 min := mid + 1
 else if c == 'l'
 max := mid - 1;
 else if c == 'y'
 return mid
 until (min > max);

However if you want more help, you will need to post your code so far.

Answer 3

getRandomNumber(lower, upper){
 return random number between lower and upper;
}
main(){
 lower = 0;
 upper = 101;
 num = getRandomNumber(lower, upper);
 response = askUser(num);
 while(response != Y){
 if (response==H)
 //if secret is higher than num
 lower = num;
 else
 //if secret is lower than num
 upper = num;
 num = getRandomNumber (lower, upper);
 response = askUser(num);
 }
}

• David Sykes: This is not really a 'binary' search, though it will get there in the end