{"problem":{"name":"「HGOI-1」Binary search","description":{"content":"众所周知二分查找的 $\\text{mid}$ 在计算时可以取 $\\lfloor\\dfrac{l+r}{2}\\rfloor$ 或者 $\\lceil\\dfrac{l+r}{2}\\rceil$，于是有选择困难症的 $\\text{bh1234666}$ 同学在自己的二分查找代码中加入了随机化，每次随机选取其中的一个作为 $\\textit{mid}$。 注意，选取不同的 mid 其他参数也会受到影响，请以","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":65536},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8481"},"statements":[{"statement_type":"Markdown","content":"众所周知二分查找的 $\\text{mid}$ 在计算时可以取 $\\lfloor\\dfrac{l+r}{2}\\rfloor$ 或者 $\\lceil\\dfrac{l+r}{2}\\rceil$，于是有选择困难症的 $\\text{bh1234666}$ 同学在自己的二分查找代码中加入了随机化，每次随机选取其中的一个作为 $\\textit{mid}$。\n\n注意，选取不同的 mid 其他参数也会受到影响，请以代码为准。\n\n现在 $\\text{bh1234666}$ 给你了二分查找使用的序列（保证为单调递增）以及他想要寻找的数（保证在序列内），他想知道在运气最好的情况下循环需要进行几次（即代码中 $\\textit{cnt}$ 的可能的最终值的最小值）。\n\n循环：\n```cpp\nint find(int *num,int x,int len)\n{\n\tint l=0,r=len-1,mid,cnt=0,w;\n\twhile(l<r)\n\t{\n\t\tcnt++;\n\t\tw=rand()%2;\n\t\tmid=(l+r+w)/2;\n\t\tif(num[mid]-w<x) l=mid+!w;\n\t\telse r=mid-w;\n\t}\n\treturn mid;\n}\n```\n递归：\n```\nint cnt;\nint get(int *num,int x,int l,int r)\n{\n\tif(l==r) return l;\n\tcnt++;\n\tint w=rand()%2;\n\tint mid=(l+r+w)/2;\n\tif(num[mid]-w<x) return get(num,x,mid+!w,r);\n\telse return get(num,x,l,mid-w);\n}\nint find(int *num,int x,int len)\n{\n\tcnt=0;\n\treturn get(num,x,0,len-1);\n}\n```\n注：以上两代码完全等价。\n\n在此对上述代码中的 $w$ 的作用做进一步阐释。\n\n例如对于区间 $[0,7]$，有 $8$ 个成员。虽然 $mid$ 的取值会因为 $w$ 的取值改变而改变，但是最终确定的区间一定是 $[0,3]$ 或 $[4,7]$，选手可以就上述代码自行模拟。\n\n对于区间 $[0,6]$，有 $7$ 个成员。$\\textit{mid}$ 的取值与 $w$ 的取值无关，但是 $l$ 和 $r$ 的取值会受到 $w$ 的影响，最终确定的区间可能是 $[0,2]$，$[3,6]$（$w=1$）或 $[0,3]$，$[4,6]$（$w=0$）。\n\n## Input\n\n第一行给出一个整数 $n$ 表示序列长度。\n\n第二行给出单调递增的 $n$ 个整数表示 $\\text{bh1234666}$ 的序列。\n\n第三行一个整数 $q$ 表示询问的次数。\n\n接下来 $q$ 行每行一个整数表示需要查询的数字。\n\n## Output\n\n对于每个询问回答一个整数，表示最小的循环次数。\n\n[samples]\n\n## Background\n\n$\\text{bh1234666}$ 正在学习[二分查找](https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/10628618?fr=aladdin)。\n\n## Note\n\n### 样例 1 解释\n\n找 $4$：\n\n取 $[1,5]$。\n\n取 $[1,3]$。\n\n取 $[3,3]$（退出循环）。\n\n### 样例 2 解释\n\n查询 $10$ 的位置。\n\n$$\n[1,13] \\stackrel{w=0}{\\longrightarrow} [1,7]\\stackrel{w=0}{\\longrightarrow}[5,7] \\stackrel{w=1}{\\longrightarrow} [5,5]\n$$\n\n### 数据范围及约定\n本题采用**捆绑测试**，共有 $3$ 个 $\\text{subtask}$，最终分数为所有 $\\text{subtask}$ 分数之和。\n\n$$\n\\def\\arraystretch{1.5}\n\\begin{array}{|c|c|c|}\\hline\n\\textbf{Task} & \\textbf{Score} & \\text{特殊限制} \\cr\\hline\n1 & 25 & n \\le 20 \\cr\\hline\n2 & 35 & n=2^k(k \\in \\mathbf{N}) \\cr\\hline\n3 & 40 &  \\cr\\hline\n\\end{array}\n$$\n\n对于 $100\\%$ 的数据，保证 $1 \\le n \\le 2^{20}$，$1 \\le q \\le 100$，$1 \\le num_i \\le 10^9$。\n\n本题有 [extra sub](https://www.luogu.com.cn/problem/P8487)。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8481","tags":["二分","洛谷原创","O2优化","深度优先搜索 DFS","洛谷月赛"],"sample_group":[["10\n1 2 4 6 7 8 10 13 15 17\n3\n4\n10\n15","3\n3\n3"],["13\n1 2 4 6 10 12 19 23 45 99 101 123 134\n5\n1\n2\n10\n19\n123\n","3\n4\n3\n3\n4"]],"created_at":"2026-03-03 11:09:25"}}