0374. Guess Number Higher or Lower

题目信息

题号:

0374

难度:

Easy

主题:

交互接口、隐藏整数、返回值语义、搜索范围

原题:

LeetCode 0374

重点:

隐藏整数位于 1 到 n、只能通过 guess 获得大小关系、正确解释 -1、0、1

题目重述

系统预先在闭区间 [1, n] 中选择一个整数 pick。平台提供 guess(num) 接口:若 num 大于 pick,返回 -1;若 num 小于 pick,返回 1;二者相等时返回 0。

实现函数并返回隐藏整数 pick。n 位于 [1, 2^31-1],平台保证 pick 一定在该范围内。程序不能直接读取 pick,只能根据多次接口调用的结果确定答案。

自建示例

隐藏数位于区间内部:

输入:n = 20,pick = 13
输出:13
解释:对小于 13 的猜测,接口返回 1;对大于 13 的猜测,接口返回 -1;猜测 13 时返回 0。

隐藏数位于上边界:

输入:n = 6,pick = 6
输出:6
解释:隐藏数可以等于 n,搜索范围包含两个端点。

接口返回值直接决定保留哪一半

维护仍可能包含 pick 的闭区间 [left, right]。猜测中点后,返回 0 立即得到答案;返回 -1 表示猜测偏大,隐藏数只能在左半;返回 1 表示猜测偏小,隐藏数只能在右半。每次更新都保留端点合法性。

C++ 实现

class Solution {
public:
    int guessNumber(int n) {
        long long left = 1;
        long long right = n;
        while (left <= right) {
            long long middle = left + (right - left) / 2;
            int result = guess(static_cast<int>(middle));
            if (result == 0) return static_cast<int>(middle);
            if (result < 0) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return -1;
    }
};

代码分析

guess 的 -1 与 1 含义恰好分别对应“猜大”和“猜小”,不能按普通比较函数的直觉反写;用 long long 计算中点避免边界加法溢出。每次调用缩小一半搜索区间,时间复杂度为 O(log n),额外空间为 O(1)。