###### tags: `leetcode` `easy` `Binary Search` `Interactive`
# [374. Guess Number Higher or Lower](https://leetcode.com/problems/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