Guess Number Higher Or Lower

374. 猜数字大小

分析

初始化搜索范围：
- 定义变量 l 和 r 分别表示搜索范围的左右边界
- 初始搜索范围为 [1, n]
二分查找：
- 计算中间值 mid = (l + r) / 2，避免溢出可以写为 (l + r) >> 1
- 调用 guess(mid) 判断中间值与目标值的关系：
- 如果返回 -1，说明目标值更小，将右边界缩小为 r = mid
- 如果返回 1，说明目标值更大，将左边界缩小为 l = mid + 1
终止条件：
- 当左右边界相遇时，搜索结束，返回 r

时间复杂度

每次查找都会将搜索范围缩小一半，直到范围缩小到 1

时间复杂度为 O(logn)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution
{
public:
    int guessNumber(int n)
    {
        int l = 1, r = n; // 初始化左右边界
        while (l < r)
        {
            int mid = (long long)l + r >> 1; // 计算中间值
            if (guess(mid) <= 0) // 若目标值小于等于 mid
                r = mid; // 缩小右边界
            else // 若目标值大于 mid
                l = mid + 1; // 缩小左边界
        }
        return r; // 返回结果
    }
};