just started to learn programming recently and i wanted to do some excericises, i came upon this list http://www.cplusplus.com/forum/articles/12974/
and as the title suggest i was doing the bracketing search exercise, im having trouble in making the program guess in 7 tries or less, here's what i made:
#include <iostream>
#include <math.h>
usingnamespace std;
int main()
{
char x;
float m, guess;
cout<<"hey there! choose a number between 1 and a number you choose and i will try to guess"<<endl
<<"type h for high, l for low and c for correct"<<endl;
cout<<"what will the maximum be?"<<endl;
cin>>m;
guess=m/2;
float change=guess;
cout<<"my first guess is "<<guess<<endl;
while(x!='c'){
change=change/2;
cin>>x;
if(x=='h'){
guess-=change;
cout<<floor(guess)<<endl;}
if(x=='l'){
guess+=change;
cout<<ceil(guess)<<endl;}
}
cout<<"thanks for playing!"<<endl;
return 0;
}
it works, but for example, if i pick the range from 1 to 100 and i choose a number like 33, it would take 8 tries to guess correctly.
To guess in 7 tries or less, you need to apply binary search. This is basically how binary search works:
1. Function is given a search target as well as a lower bound and upper bound to search in.
2. If lower bound is greater than upper bound, search target does not exist in range.
3. If middle element of range is the search target, you're done.
4. If middle element is smaller than search target, then change lower bound to middle element + 1.
5. If middle element is larger than search target, then change upper bound to middle element - 1.
6. Go to 2.