0300 - 0399
0374 - Guess Number Higher or Lower (Easy)
Problem Link
https://leetcode.com/problems/guess-number-higher-or-lower/
Problem Statement
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.
You call a pre-defined API int guess(int num), which returns three possible results:
-1: Your guess is higher than the number I picked (i.e.num > pick).1: Your guess is lower than the number I picked (i.e.num < pick).0: your guess is equal to the number I picked (i.e.num == pick).
Return the number that I picked.
Example 1:
Input: n = 10, pick = 6
Output: 6Example 2:
Input: n = 1, pick = 1
Output: 1Example 3:
Input: n = 2, pick = 1
Output: 1Constraints:
1 <= n <= 2^31 - 11 <= pick <= n
Approach 1: Binary Search
See Binary Search for basic understanding.
/**
* Forward declaration of guess API.
* @param num your guess
* @return -1 if num is higher than the picked number
* 1 if num is lower than the picked number
* otherwise return 0
* int guess(int num);
*/
class Solution {
public:
int guessNumber(int n) {
int l = 1, r = n;
while (l < r) {
// middle point
int m = l + (r - l) / 2;
// check the result
int x = guess(m);
// found the answer
if (x == 0) return m;
// exclude m
else if (x == 1) l = m + 1;
// include m
else r = m;
}
return l;
}
};