-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!
Here "My" means the number which is given for you to guess not the number you put into guess(int num).
@Nakanu
Here is my simple code.
public class Solution extends GuessGame {
public int guessNumber(int n) {
return bsearch(1,n);
}
private int bsearch(int start,int end){
if(start>end) return -1;//R u kidding me?
if(guess(start)==0) return start;
if(guess(end)==0) return end;
int mid = start+(end-start)/2;
if(guess(mid)==0) return mid;
else if(guess(mid)==-1) return bsearch(start+1,mid-1);
else return bsearch(mid+1,end-1);
}
}
Edit: I have removed the redundant parameter of the bsearch function. Thanks to guhan!
It's not key point. There is no global definition that states my means the result generated from guessNumber API. Infact, from general English viewpoint, my number would mean the number that is generated by me, my method ergo my number. I hope they make the question definition more clear.
@krutarthjoshi18
You are right. There is no global definition about it. But there are some habits which people have already cultivated. In China, when I was a child, the person who hosts the game will tell you if the number you give is bigger or smaller than the right answer. I believe that misled lots of Chinese here. XD. Anyway, the problem itself is not that hard. And I have got a lesson that I really need to read and understand the problem itself carefully. That is the key point.
@krutarthjoshi18 The entire problem is consistently told from the view of the game master in the first person and the guesser in the second person. Why would you assume that that changes in the middle? And then changes back for the example? And even if you do somehow manage that mental somersault, how could the API return value descriptions possibly be from the view of the guesser? Why would the guesser say "Congrats! You got it!"? Makes no sense.
The problem is fine as it is.
@Nakanu I don't think you need to pass the first parameter 'n' in the recursive function.
Hello, the whole point of binary search is to check as little as possible. There's no need to have separate ifs for start and end.
public int binSearch(int min, int max) {
int mid = min + (max - min)/2;
if (guess(mid) == 0) {
return mid;
} else if (guess(mid) == -1) {
return binSearch(min, mid);
} else {
return binSearch(mid + 1, max);
}
}
Yeah, I come here just to complain about the confusing description.
But since leetcode has already supported stdout, it's debuggable at least ;)
// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);
class Solution {
public:
int guessNumber(int n) {
int lo = 1, hi = n;
while (lo <= hi) {
int mi = (hi-lo >> 1) + lo;
//cout << lo << " " << hi << " " << mi << endl;
int cmp = guess(mi);
if (cmp > 0) lo = mi + 1;
else if (cmp < 0) hi = mi - 1;
else return mi;
}
return -1;
}
};