寻求满足非递增约束的O(n)时间猜数算法（每轮⌈log n⌉次猜测）

我们需要解决的猜数游戏问题如下：

• 游戏规则：每次猜测1~n范围内的整数，每轮最多允许⌈log₂n⌉次猜测，猜测后会收到「过大」或「过小」的经典反馈。
• 轮次约束：共进行m轮游戏（m < n），所有轮次的正确答案构成非递增数组M[1..m]（即任意i > j，M[i] ≤ M[j]）。
• 目标：设计总时间复杂度为O(n)的算法，替代常规的O(m·logn)方案，且禁止暴力逐个猜数。

核心思路是利用答案的非递增特性，通过「区间分段跳跃+二分搜索」的组合策略，平摊总猜测次数到O(n)，同时严格遵守每轮最多⌈log₂n⌉次猜测的限制。

1. 初始轮次处理 #

第一轮无前置约束，直接使用标准二分搜索在[1, n]范围内查找M[1]，最多消耗⌈log₂n⌉次猜测，完成后记录当前的搜索上界current_high = M[1]，下界保持为1。

2. 后续轮次的分段搜索策略 #

从第二轮开始，每轮的搜索区间初始为[1, current_high]，执行以下步骤：

• 步骤1：跳跃式预验证
  计算跳跃步长step = ⌈log₂n⌉，猜测current_high - step：
  • 若反馈为「过大」：说明当前轮答案M[i] < current_high - step，直接将current_high更新为current_high - step，重复此预验证步骤（直到current_high - step < 1或反馈变为「过小」）。
  • 若反馈为「过小」：说明当前轮答案M[i] ∈ [current_high - step + 1, current_high]，进入步骤2。
• 步骤2：区间内二分搜索
  在当前缩小后的区间内执行标准二分搜索，找到M[i]。由于区间长度最大为step = ⌈log₂n⌉，二分搜索最多消耗⌈log₂(step)⌉次猜测，远小于⌈log₂n⌉，满足每轮次数限制。
• 步骤3：更新上界
  将current_high更新为M[i]，为下一轮搜索做准备。

3. 平摊复杂度分析 #

• 每经过step次数值的下降，我们仅消耗O(logn)次猜测（预验证+二分），因此总猜测次数为O(n / step * logn)。由于step = ⌈log₂n⌉，代入后总次数为O(n / logn * logn) = O(n)，符合时间复杂度要求。
• 每轮的猜测次数：预验证最多1次（因为每次跳跃后区间直接收缩），加上二分的O(loglogn)次，总次数远小于⌈log₂n⌉，满足每轮次数限制。

示例验证（n=100，⌈log₂100⌉=7） #

以示例数组{98,88,76,76,76,74,65,43,43,42}为例：

1. 第一轮二分查找98，用7次猜测，current_high=98。
2. 第二轮：猜测98-7=91，反馈「过大」，更新current_high=91；再猜91-7=84，反馈「过小」，在[85,91]内二分找到88，用3次猜测，总次数1+3=4 <7。
3. 第三轮：猜测88-7=81，反馈「过大」，更新current_high=81；再猜81-7=74，反馈「过小」，在[75,81]内二分找到76，用3次猜测，总次数1+3=4 <7。
4. 后续三轮答案都是76，直接猜测current_high=76，反馈正确，每轮仅1次猜测，远小于7次。
5. 剩余轮次重复上述逻辑，总猜测次数最终控制在O(100)=O(n)范围内。

内容的提问来源于stack exchange，提问作者mouse