Binary search use in simple guessing game

Question

I'm making a simple guessing game in C. Basically what I need is some help double-checking my work, more specifically a verification that the my binary search in my case statements look okay. The goal is to have an initial guess of 50, then work off that. If "L" is selected, the search goes from 51-100, if "H", it would be 1-49, blah-blah - the usual stuff scaling down to the correct guess.

Is this correct?

I'm also getting a C99 function implementation error using the actual letters as case labels -- just to explain why they're the ASCII equivalents.

#include <stdio.h>
#include <ctype.h>
int main(int argc, const char * argv[])
{
int low;
int high;
int guess;
int response;
 printf("Pick an integer from 1 to 100 and I will try to guess it.\n");
 printf("If I guess too low, respond with a L.\n");
 printf("If I guess too high, respond with a H.\n");
 printf("If I guess correctly, respond with a Y.\n");
high = 100;
low = 1;
while(response != 'Y')
{
guess = (high + low) / 2;
printf("Okay, let's start. Is it %d?\n", &guess);
printf("Please respond with L, H, or Y.\n");
scanf("%d", &response);
response = toupper(response);
switch(response)
{
 case 72: high = guess - 1;
 break;
 case 76: low = guess + 1;
 break;
 case 89: printf("Yes! I knew I could do it.\n");
 break;
 default: printf("I didn't get that; you gave an invalid response.\n");
 printf("Please try again.\n"); 
}
}
return 0;
}

• syb0rg: The "C99 function implementation error" that you are experiencing is because you have not enabled C99 mode with your compiler; it isn't because C99 doesn't support it.
• petrichor: Interesting! That's really good to know. Thank you for this! @syb0rg
• Malachi: sounds almost like the beginning of a sort method too. you could probably adapt it at some point...just saying my thoughts when I read the first paragraph

Answer 1

I'm thoroughly puzzled by your use of the response variable.

The condition for the while-loop is response != 'Y'. The first time through, response is an uninitialized variable, containing any imaginable int value. So, the behaviour of your program is undefined.

response is an int. Why are you comparing it to 'Y'? That makes 89 a special number.

If we make it inside the loop, you ask the user to enter a character 'L', 'H', or 'Y', but actually read an integer. If you actually enter one of those three characters, scanf() will fail to read an integer; your program will consider the input to be invalid, and it will loop forever, since scanf() will immediately fail again, etc. There are only two ways to terminate your program: CtrlC or by typing 89Enter at the prompt.

Then you call toupper() on the integer; the toupper() function only makes sense for translating a letter to its uppercase counterpart. (The toupper() function takes an int instead of a char only because it is meant to support EOF, or -1, as a value.)

Then, in the switch block, you have magic numbers 72, 76, and 89. Magic numbers should not exist in your code.

---

Your first printf() call is also wrong. It should be

printf("Okay, let's start. Is it %d?\n", guess);

since &guess would print the address of the guess variable instead of its contents. Your compiler should have warned you about that mistake. You should have heeded the warning, as well as tested your code.

Answer 2

• If you're not going to use the command line parameters, replace them with a single void (only for C):

  int main(void) {}
  

• Everything within curly braces, especially main(), should be indented. This should also be done consistently, not just in some select or random places.

• Don't just list variable declarations at the start of a function by default:

  int low;
  int high;
  int guess;
  int response;
  

  It's best to initialize them as close to their use as possible, that way you'll know where they belong and if they're still in use while maintaining the code.

  For instance, high and low can be initialized right away:

  int high = 100;
  int low = 1;
  

• For unformatted outputs, such as the first four outputs, prefer puts() over printf(). Also note that the former adds an automatic "\n" at the end of the output.

• Other reviewers have mentioned instances of broken code. You should compile at a high warning level with the -Wall flag and (ideally) have them treated as compiler errors with -Werror. More info about GCC compiler flags here.

• Malachi: really guess could be initialized right away as well, and we could skip the calculation the first time around, but that might make more work for this program
• Jamal: @Malachi: Right. I've just mentioned those first two as they're the first to appear, and it should still give the OP the right idea.

Answer 3

Looks good to me. I can only nitpick:

• Instead of printf("...\n"), it's better to use puts("...")
• If you really must use the ASCII codes, then at least add a comment there to know that 72 is H, 76 is L, and so on.
• You should indent code blocks within braces { ... }, for example the body of the main method and the while loop. Near the end of the code it's confusing to see several lines with unindented }, I lose track of which one closes what...

• petrichor: Good call on the commenting to denote the ASCII. Will do.
• user33739: Why is puts() preferable? Is because of the implied newline?
• janos: @piperchester since puts does't need to handle formatting characters, it has a simpler implementation = smaller possiblity of bugs = faster. And yes, if you want to print a newline anyway, then puts is less typing, so more convenient.

Answer 4

Your indentation is off.

---

you aren't actually using the program arguments, so there isn't any reason to include them in your main signature.

---

I was able to compile and run using case 'H':, perhaps I wasn't using c99. So perhaps just don't use c99 :). If you have to use it, then declare those ints as symbols or consts above #DEFINE H 72, then you can say case H:

---

A do-while loop would logically serve you better here. Aditionally, because you didn't give response a default value, who knows what garbage is in it, maybe it actually is 'Y'.

---

I typically don't place code on the same line as case <>: unless I am 1-lining the whole thing.

---

You didn't include a break on your default condition, this isn't wrong, I just want to point out that some people like to see it for consistency's sake.

---

I like my variables to only be in the scope they are needed. For your case this would be guess not being in the loop.

---

Edited additional points

In this line printf("Okay, let's start. Is it %d?\n", &guess); you'll notice that you are printing the address of guess not the value of guess as denoted by the &, remove this if you want your program to run properly.

---

Point of affirmation, this is indeed a good binary search. finding halfway between your highest and lowest values will get you to the answer on average the quickest.

---

All the changes:

#include <stdio.h>
#include <ctype.h>
int main(int argc, const char * argv[])
{
 printf("Pick an integer from 1 to 100 and I will try to guess it.\n");
 printf("If I guess too low, respond with a L.\n");
 printf("If I guess too high, respond with a H.\n");
 printf("If I guess correctly, respond with a Y.\n");
 int low = 1;
 int high = 100;
 int response;
 do
 {
 int guess = (high + low) / 2;
 printf("Okay, let's start. Is it %d?\n", guess);
 printf("Please respond with L, H, or Y.\n");
 scanf("%d", &response);
 response = toupper(response);
 switch(response)
 {
 case 'H': high = guess - 1; break;
 case 'L': low = guess + 1; break;
 case 'Y': printf("Yes! I knew I could do it.\n"); break;
 default: printf("I didn't get that; you gave an invalid response.\nPlease try again.\n"); break;
 }
 } while(response != 'Y');
 return 0;
}

• petrichor: Awesome! Thank you so much :) Does my binary search algorithm setup look okay? I'm a little unsure about it being correct or not, took me forever to figure out.
• syb0rg: You probably were using C99 when you put the characters in the switch. Depending on your compiler configuration, it may or may have not generated a warning though.
• Cu3PO42: Both gcc and clang compile the version with chars just fine for me. I currently also don't see why they wouldn't? What definitely should work is (int)'H'...
• BenVlodgi: @petrichor, I added a couple points, including a remark on your searching.
• Snowbody: C99 doesn't let you compare a character literal to an int? but it shouldn't be an int anyway.

Answer 5

I'm late to the game, but here are a few notes that I didn't see mentioned:

• I already went over this in the comments, but when you said that you have a "C99 function implementation error", that is because you haven't set you compiler standard support to C99. With GCC, you can do this with --std=c99. But why would we use the C99 standard when the current standard is C11? And what if we want some useful GNU extensions? You can enable those in GCC with either --std=c11 or --std=gnu11. I would recommend at least using the C11 standard.

• Extrapolate your block of text you want to output to the console into its own string.

  const char introMessage[] =
   "Pick an integer from 1 to 100 and I will try to guess it.\n"
   "If I guess too low, respond with a L.\n"
   "If I guess too high, respond with a H.\n"
   "If I guess correctly, respond with a Y.\n";
  

  Then printing is a bit more simple, and reusable if needed (such as if you want to play the game again without quitting the application).

  puts(introMessage);
  

  This is the more common approach to printing large blocks of text in the real world, especially when you have to print it out multiple times.

• This was already mentioned, but it needs to be emphasized. You need to watch your indentation. It improves readability by a lot, allowing you to comprehend and produce code more quickly.

• You don't have to return 0 at the end of main(), just like you wouldn't bother putting return; at the end of a void-returning function. The C standard knows how frequently this is used, and lets you not bother.

  C99 & C11 §5.1.2.2(3)

  ...reaching the } that terminates the main() function returns a value of 0.

• Jamal: I'm not quite sure about the second point. I have heard that it's not worth having a function just for output. I guess it doesn't always matter.
• syb0rg: @Jamal I thought I had seen that in use with publicly available code, but now it uses a different (and better IMO) method. I have revised my answer accordingly.

Answer 6

I too am late to the game. Let's see what I can make of this code.

I would merge some things together, like your print statements. There are two places in which you have two print statements where one would be sufficient. I have moved them around, and hopefully I didn't murder C in any way by doing this.

I also stole the do while from Master BenVlodgi.

Another thing that I did was to change the scanf() to a getchar(). I don't know much about C, but this sounds like it should do what you want it to as long as you are looking for a single character response.

Do this:

do
{
 guess = (high + low) / 2;
 printf("Okay, let's start. Is it %d?\n Please respond with L, H, or Y.\n", guess);
 response = toupper(getchar());
 switch(response)
 {
 case 'H': high = guess - 1;
 break;
 case 'L': low = guess + 1;
 break;
 case 'Y': printf("Yes! I knew I could do it.\n");
 break;
 default: printf("I didn't get that; you gave an invalid response.\n Please try again.\n"); 
 }
}while(response != 'Y');

instead of this:

while(response != 'Y')
{
 guess = (high + low) / 2;
 printf("Okay, let's start. Is it %d?\n", guess);
 printf("Please respond with L, H, or Y.\n");
 scanf("%d", &response);
 response = toupper(response);
 switch(response)
 {
 case 72: high = guess - 1;
 break;
 case 76: low = guess + 1;
 break;
 case 89: printf("Yes! I knew I could do it.\n");
 break;
 default: printf("I didn't get that; you gave an invalid response.\n");
 printf("Please try again.\n"); 
 }
}