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)``。