374. Guess Number Higher or Lower

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 3 possible results:

  • -1: The number I picked is lower than your guess (i.e. pick < num).
  • 1: The number I picked is higher than your guess (i.e. pick > num).
  • 0: The number I picked is equal to your guess (i.e. pick == num).

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

Example 4:

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

 

Constraints:

  • 1 <= n <= 231 - 1
  • 1 <= pick <= n

Rust Solution

struct Solution;

static mut X: i32 = 0;

unsafe fn guess(num: i32) -> i32 {
    use std::cmp::Ordering::*;
    match X.cmp(&num) {
        Equal => 0,
        Greater => 1,
        Less => -1,
    }
}

impl Solution {
    #[allow(non_snake_case)]
    unsafe fn guessNumber(n: i32) -> i32 {
        let mut l = 1;
        let mut r = n;
        while l < r {
            let m = l + (r - l) / 2;
            match guess(m) {
                0 => {
                    return m;
                }
                -1 => {
                    r = m;
                }
                1 => {
                    l = m + 1;
                }
                _ => {}
            }
        }
        l
    }
}

#[test]
fn test() {
    unsafe {
        X = 6;
        assert_eq!(Solution::guessNumber(10), 6);
    }
}

Having problems with this solution? Click here to submit an issue on github.