#2184. 猜数字大小
猜数字大小
我们正在玩猜数字游戏。猜数字游戏的规则如下:
我会从 1
到 n
随机选择一个数字。 请你猜选出的是哪个数字。(二分法)
输出要猜的次数。
格式
输入
第一行 :n 第二行:选择的数字
输出
查找的次数
样例1
10
4
3
解释
在有序数组 [1,2,3,4,5,6,7,8,9,10]
中查找 3
,二分查找步骤如下:
- 中间值
5
(比较 1 次),3 < 5
,缩小至左半部分。 - 中间值
2
(比较 2 次),3 > 2
,缩小至右半部分。 - 中间值
3
(比较 3 次),找到目标。 总查找次数为 3。
样例2
8
8
4
解释
在有序数组 [1,2,3,4,5,6,7,8]
中查找 8
,二分查找步骤如下:
- 中间值
4
(比较 1 次),8 > 4
,缩小至右半部分。 - 中间值
6
(比较 2 次),8 > 6
,缩小至右半部分。 - 中间值
7
(比较 3 次),8 > 7
,缩小至右半部分。 - 中间值
8
(比较 4 次),找到目标。 总查找次数为 4。
样例3
7
4
1
解释
在有序数组 [1,2,3,4,5,6,7]
中查找 4
,第一次中间值即为 4
(比较 1 次),直接找到目标。
提示:
1 <= n <= 2<sup>31</sup> - 1
1 <= pick <= n