#2184. 猜数字大小

猜数字大小

我们正在玩猜数字游戏。猜数字游戏的规则如下:

我会从 1n 随机选择一个数字。 请你猜选出的是哪个数字。(二分法)

输出要猜的次数。

格式

输入

第一行 :n 第二行:选择的数字

输出

查找的次数

样例1

10
4
3

解释 在有序数组 [1,2,3,4,5,6,7,8,9,10] 中查找 3,二分查找步骤如下:

  1. 中间值 5(比较 1 次),3 < 5,缩小至左半部分。
  2. 中间值 2(比较 2 次),3 > 2,缩小至右半部分。
  3. 中间值 3(比较 3 次),找到目标。 总查找次数为 ​3​。

样例2

8
8
4

解释 在有序数组 [1,2,3,4,5,6,7,8] 中查找 8,二分查找步骤如下:

  1. 中间值 4(比较 1 次),8 > 4,缩小至右半部分。
  2. 中间值 6(比较 2 次),8 > 6,缩小至右半部分。
  3. 中间值 7(比较 3 次),8 > 7,缩小至右半部分。
  4. 中间值 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