How to write a binary algorithm for C/C++
-
18-09-2019 - |
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.
Solution
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]
OTHER TIPS
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.
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);
}
}