Bracketing Search Exersice

[miatech]

guys, I'm working on an problem in which the computer is guessing the number the user is thinking. but the guesses are not quite working. And I think is because the implementation of the guessHigh and guessLow methods. Any help appreciated. Here's the problem.
--------------------------------------------------------------------------------

Write a program that calculates a random number 1 through 100. The program then asks the user to guess the number.
If the user guesses too high or too low then the program should output "too high" or "too low" accordingly.
The program must let the user continue to guess until the user correctly guesses the number.

Modify the program so that instead of the user guessing a number the computer came up with, the computer guesses the number that the user has secretly decided. The user must tell the computer whether it guessed too high or too low.

what I have so far.

#include <iostream>
#include <Windows.h>
using namespace std;
void startGame();
void guessNum(int n);
int guessHigh(int l, int h);
int guessLow(int l, int h);
void guessRight(int n);
int low = 50, high = 100, count = 0, num = 50;
int main()
{
	startGame();
	system("pause");
	return 0;
}

void startGame()
{
	cout << "Think a number from 1 - 100. \n";
	Sleep(5000);
	guessNum(num);
}
void guessNum(int num)
{
	char a;
	do
	{
		cout << "Is your number " << num << " ?\n";
		cout << "Enter (c) for correct\n";
		cout << "Enter (l) if number is low\n";
		cout << "Enter (h) if number is too high\n";
		cout << "Enter (q) to quit\n";
		cin >> a;
		if(a == 'c') { guessRight(num); }
		else if(a == 'l') { num = guessHigh(high, low); }
		else if(a == 'h') { num = guessLow(high, low); }
		else if(a == 'q') { cout << "Goodbye!\n"; break; }
		else { cout << "Wrong choice try again\n"; }
		count++;
	}while(a != 'q');
}
int guessHigh(int l, int h)
{
	int n = (h + l) / 2;
	high = l; low = n;
	return n;
}
int guessLow(int l, int h)
{
	int n = (h - l) / 2;
	high = l; low = n;
	return n;
}
void guessRight(int n)
{
	cout << "Congrats, you guessed in " << count << " tries!\n";
	startGame();
}

[jsmith]

The problem is that lines 45 and 51 don't actually do anything. Neither high nor low is ever changed.

[miatech]

I guess the assigment of low and high should be made before calling the function b/c the low and high change in dependence of which function is called.... I could be wrong

[hanst99]

Actually, guessLow will work as intended. guessLow is wrong though. What I don't really get is why you make a difference between high and low, you could do it with binary search using only one variable.

[miatech]

could you link me somewhere that is explained.... I'm doing searches by "binary search" but none of the tutorials I've seen are applicable to this scenario

thanks

[hanst99]

Well, actually yes. You are looking for an unknown value, and you always know whether the value you search for is higher or lower than the current value, and the values are ordered (yay for Maths: You have the set of natural numbers lower than 101 excluding 0. That set is, by definition, ordered). Means you can use binary search. I know, most tutorials use this to find indices of arrays or something like that, but you can use it to guess a number just as easily.

Copied straight from wikipedia:

This rather simple game begins something like "I'm thinking of an integer between forty and sixty inclusive, and to your guesses I'll respond 'High', 'Low', or 'Yes!' as might be the case." Supposing that N is the number of possible values (here, twenty-one as "inclusive" was stated), then at most \lceil\log_2 N\rceil questions are required to determine the number, since each question halves the search space. Note that one less question (iteration) is required than for the general algorithm, since the number is already constrained to be within a particular range.

Even if the number to guess can be arbitrarily large, in which case there is no upper bound N, The number can be found in at most 2\lceil \log_2 k \rceil steps (where k is the (unknown) selected number) by first finding an upper bound by repeated doubling.[citation needed] For example, if the number were 11, the following sequence of guesses could be used to find it: 1, 2, 4, 8, 16, 12, 10, 11

One could also extend the method to include negative numbers; for example the following guesses could be used to find −13: 0, −1, −2, −4, −8, −16, −12, −14, −13.

[miatech]

jsmith was right... variables: low and high are never changed... how's that?

[jsmith]

You call guessHigh and guessLow with the values high and low (in that order). In each function high is set to the value of the first parameter (which is high) and low is set to the value of the second parameter (which is low). So in effect,

high = l;  // is the same as
high = high;

low = h;  // is the same as
low = low;

[miatech]

I was able to get it working passing by & reference, but what would I have to do if I wanted to pass by value instead?