tags: leetcode easy Binary Search Interactive

374. Guess Number Higher or Lower

Description

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.

Examples

Example 1:

Input: n = 10, pick = 6
Output: 6

Example 2:

Input: n = 1, pick = 1
Output: 1

Example 3:

Input: n = 2, pick = 1
Output: 1

Constraints:

• $1\leq n\leq 2^{31} - 1$
• $1\leq pick\leq n$

Code

/** 
 * 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);
 */

int guessNumber(int n){
	if(n == 1)
        return 1;
    int top = n, num = n / 2, down = 1, guessResult = guess(num), tmp;
    while(1){
        //Equal
        if(guessResult == 0)
            return num;
        //Higher
        if(guessResult == -1){
            top = num;
            num = floor(num / 2.0 + down / 2.0);
        }
        //Lower
        if(guessResult == 1){
            down = num;
            num = ceil(num / 2.0 + top / 2.0);
        }
        guessResult = guess(num);
    }
}

Complexity

Space	Time
$O(1)$	$O(\log(n))$

Result

• Runtime: 3 ms, 42.47%
• Memory Usage: 5.4 MB, 95.11%

Notes

• Binary search
• Integer overflow