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``,只能根据多次接口调用的结果确定答案。 自建示例 -------- 隐藏数位于区间内部: .. code-block:: text 输入:n = 20,pick = 13 输出:13 解释:对小于 13 的猜测,接口返回 1;对大于 13 的猜测,接口返回 -1;猜测 13 时返回 0。 隐藏数位于上边界: .. code-block:: text 输入:n = 6,pick = 6 输出:6 解释:隐藏数可以等于 n,搜索范围包含两个端点。 接口返回值直接决定保留哪一半 ------------------------------ 维护仍可能包含 ``pick`` 的闭区间 ``[left, right]``。猜测中点后,返回 ``0`` 立即得到答案;返回 ``-1`` 表示猜测偏大,隐藏数只能在左半;返回 ``1`` 表示猜测偏小,隐藏数只能在右半。每次更新都保留端点合法性。 C++ 实现 -------- .. code-block:: cpp 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(middle)); if (result == 0) return static_cast(middle); if (result < 0) { right = middle - 1; } else { left = middle + 1; } } return -1; } }; 代码分析 -------- ``guess`` 的 ``-1`` 与 ``1`` 含义恰好分别对应“猜大”和“猜小”,不能按普通比较函数的直觉反写;用 ``long long`` 计算中点避免边界加法溢出。每次调用缩小一半搜索区间,时间复杂度为 ``O(log n)``,额外空间为 ``O(1)``。