0374.猜数字大小.md

解题关键点

• 很常规的二分法，时间复杂度 O(logn)，空间复杂度 O(1)

代码

impl Solution {
    unsafe fn guessNumber(n: i32) -> i32 {
        let mut left = 1;
        let mut right = n;
        while left <= right {
            // 直接 (left + right) / 2 会导致溢出，所以要曲线救国
            let mid = left + (right - left) / 2;
            match guess(mid) {
                -1 => {
                    right = mid;
                }
                1 => {
                    left = mid + 1;
                }
                // rust 中 match 的所有条件必须能够覆盖全部 case，所以这里不能写 0
                _ => {
                    return mid;
                }
            }
        }
        // 必须返回一个合法的类型，所以这里随便返回个值，反正也执行不到这里……
        n
    }
}

测试用例

还需要一个辅助函数 guess