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.

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

You should also describe what your troubles are. Don't know what the binary search algorithm is? Try wikipedia. Don't know how to implement it in C/C++? Then tell us where you get stuck.

Answer 3

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 4

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);
 }
}