374. Guess Number Higher or Lower

Description of the Problem

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: 6

Example 2:

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

Example 3:

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

Constraints:

• 1 <= n <= 2^31 - 1
• 1 <= pick <= n

Solution

Code(Rust)

impl Solution {
    unsafe fn guessNumber(n: i32) -> i32 {
        let mut begin = 1;
        let mut i_end = n;
        let mut mid;
        loop{
            mid = begin + (i_end - begin) / 2;
            match guess(mid) {
                -1 => {i_end = mid - 1},
                0 => {break},
                1 => {begin = mid + 1},
                _ => panic!(),
            }
        };
        return mid;
    }
}

Complexity

• m is size of the range

Time complexity:

• \( T(m) = O(\log_2(m)) \)

Auxiliary Space:

• \( S(m) = O(1) \)