The Binary Search Algorithm

[coolProgramer5]

Hi, I'm trying to write a program that plays a simple number-guessing with its user. The user thinks of a number and then answers a series of questions asked by the computer until it correctly guesses the number. I wrote as much as i could think of which isn't much. I'm stuck on the part where the computer generates a yes or no question. Please help.

#include <stdio.h>
#include "simpio.h"
#include "strlib.h"
#include "genlib.h"

int main()
{
    printf("This is a guessing where I(the computer) ask you  questions until i guess your number");
    printf("And when i guess your number press ctrl+c\n\n\n");
    string yesno;
    char quit;
    int g;
    int high, low;
    printf("Enter the range\n");
    printf("low\n");\
    low=GetInteger();
    printf("high\n");
    high = GetInteger();
    printf("Think of a number from %d to %d\n\n", low, high);
    g=(low+high)/2;
    printf("is your number %d?\n", g);
    yesno=GetLine();
    while ((quit=getchar()) != EOF)
    {
          if(StringEqual(yesno, "yes"))
          {
                        printf("I guessed your number!\n");
          }
    }
    return 0;
    getchar();
}

thats all i could think of. I know it's not much but at least its something.

[jsmith]

What are you stuck on? How to do a binary search?

Given a range of integers [ min .... max ] inclusive, min <= max, generate the integer value exactly half way
between min and max (rounding if necessary) and guess that number. Call that number "guess". If guess
is less than the number chosen, then the chosen number must be in the range [ guess + 1 ... max ], inclusive,
otherwise it must be in the range [ min ... guess - 1 ] inclusive. Repeat the algorithm until the computer
guesses successfully.

[coolProgramer5]

ok.

[coolProgramer5]

I figured out the program however, is there a way to make the program more efficient? Is there a way to make the number of times the program guesses decline?

#include "strlib.h"
#include "random.h"
#include "genlib.h"

int main()
{
    printf("This is a guessing where I(the computer) ask you  questions until i guess your number");
    printf("And when i guess your number press ctrl+c\n\n\n");
    string yesno;
    char quit;
    int g;
    int high, low;
    printf("Enter the range\n");
    printf("low\n");\
    low=GetInteger();
    printf("high\n");
    high = GetInteger();
    printf("Think of a number from %d to %d\n\n", low, high);
    g=(low+high)/2;
    while (low <= high)
    {
          printf("is it %d?\n", g);
          yesno=GetLine();
          if(StringEqual(yesno, "yes"))
          {
                                printf("I guessed your number!\n");
                                break;
          }
          if(StringEqual(yesno, "no"))
          {
                          printf("is it lower then %d\n", g);
                          yesno=GetLine();
                          if(StringEqual(yesno, "no"))
                          {
                          g+=1;                      
                          }
                          else 
                          {
                           g-=1;    
                          }
          }
    }
    getchar();
    return 0;
}      

[jsmith]

The perfect algorithm will take on average O( log N ) guesses, where N is the number of values to guess from.

If the human knows the algorithm you use, the human can select a number that will always cause your algorithm
to hit its worst case. (Consider the range 1..10. Human knows computer will guess 5, then 7, then 9, then 8,
so if the human chooses 8, that is the worst case scenario).

You can mitigate this a bit by choosing a somewhat random starting guess.

[coolProgramer5]

OK i made the first guess random however, the 'random guess' is always the value of high.

#include <stdio.h>
#include "simpio.h"
#include "strlib.h"
#include "random.h"
#include "genlib.h"

int main()
{
    printf("This is a guessing where I(the computer) ask you  questions until i guess your number");
    printf("And when i guess your number press ctrl+c\n\n\n");
    string yesno;
    char quit;
    int g;
    int high, low;
    printf("Enter the range\n");
    printf("low\n");\
    low=GetInteger();
    printf("high\n");
    high = GetInteger();
    printf("Think of a number from %d to %d\n\n", low, high);
    g=rand() % low + high;
    while (low <= high)
    {
          printf("is it %d?\n", g);
          yesno=GetLine();
          if(StringEqual(yesno, "yes"))
          {
                                printf("I guessed your number!\n");
                                break;
          }
          if(StringEqual(yesno, "no"))
          {
                          printf("is it lower then %d\n", g);
                          yesno=GetLine();
                          if(StringEqual(yesno, "no"))
                          {
                          g+=1;                      
                          }
                          else 
                          {
                           g-=1;    
                          }
          }
    }
    getchar();
    return 0;
}

[jsmith]

To generate a random number in the range [0...x): rand() % x
To generate a random number in the range [k...x+k): rand() % x + k

[helios]

Typically, the formula is x%(max-min)+min.

[jsmith]

Well I was hoping OP could at least work that part out himself from the clues I gave.

[helios]

I was actually correcting OP, not you.

[coolProgramer5]

I think i got it. Thanks for helping guys. =}