P8481 「HGOI-1」Binary search

$\text{bh1234666}$ 正在学习[二分查找](https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/10628618?fr=aladdin)。

众所周知二分查找的 $\text{mid}$ 在计算时可以取 $\lfloor\dfrac{l+r}{2}\rfloor$ 或者 $\lceil\dfrac{l+r}{2}\rceil$，于是有选择困难症的 $\text{bh1234666}$ 同学在自己的二分查找代码中加入了随机化，每次随机选取其中的一个作为 $\textit{mid}$。 注意，选取不同的 mid 其他参数也会受到影响，请以代码为准。 现在 $\text{bh1234666}$ 给你了二分查找使用的序列（保证为单调递增）以及他想要寻找的数（保证在序列内），他想知道在运气最好的情况下循环需要进行几次（即代码中 $\textit{cnt}$ 的可能的最终值的最小值）。 循环： ```cpp int find(int *num,int x,int len) { int l=0,r=len-1,mid,cnt=0,w; while(l

无

无

### 样例 1 解释 找 $4$： 取 $[1,5]$。 取 $[1,3]$。 取 $[3,3]$（退出循环）。 ### 样例 2 解释 查询 $10$ 的位置。 $$ [1,13] \stackrel{w=0}{\longrightarrow} [1,7]\stackrel{w=0}{\longrightarrow}[5,7] \stackrel{w=1}{\longrightarrow} [5,5] $$ ### 数据范围及约定 本题采用**捆绑测试**，共有 $3$ 个 $\text{subtask}$，最终分数为所有 $\text{subtask}$ 分数之和。 $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \textbf{Score} & \text{特殊限制} \cr\hline 1 & 25 & n \le 20 \cr\hline 2 & 35 & n=2^k(k \in \mathbf{N}) \cr\hline 3 & 40 & \cr\hline \end{array} $$ 对于 $100\%$ 的数据，保证 $1 \le n \le 2^{20}$，$1 \le q \le 100$，$1 \le num_i \le 10^9$。 本题有 [extra sub](https://www.luogu.com.cn/problem/P8487)。