374.guess-number-higher-or-lower.md

問題

https://leetcode.com/problems/guess-number-higher-or-lower/

回答

初回の回答: 1..n の数を二分探索する

1..n の中の数を当てるにあたって、n 回 guess したらそりゃいつかは当たるんだけど、それだと線形探索になってしまう。ので、guess()の返り値を使って二分探索する。

• 1 が返ってきたら予想した値は当てる値より大きいので、下半分に絞って再び二分探索する
• -1 が返ってきたら予想した値は当てる値より小さいので、上半分に絞って再び二分探索する

/**
 * 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
 * unsafe fn guess(num: i32) -> i32 {}
 */

impl Solution {
    unsafe fn guessNumber(n: i32) -> i32 {
        let mut left = 1;
        let mut right = n;
        while left <= right {
            let middle = left + (right - left) / 2;
            match guess(middle) {
                0 => return middle,
                1 => left = middle + 1,
                -1 => right = middle -1,
                _ => panic!("invalid guess")
            }
        }
        panic!("not found");
    }
}