二分查找相关问题 -- O(n) with Conditions

Question

在游戏中，您的目标是猜测 1 到 n 范围内的数字。每轮最多允许进行 (log(n) + 1) 次猜测。在 m 轮的过程中（其中 m < n), you record the correct answers in an array M[i], with i starting from 1 to m. Initially, designing an algorithm that runs in O(m*log(n)) time is straightforward. However, a new condition has been introduced: M[i] ≤ M[j] for all i > j，这意味着答案按降序排列。任务是找到一种在给定修改条件的情况下在 O(n) 时间内运行的算法。

基于条件 M[i] ≤ M[j]（对于所有 i > j），我可以将范围缩小到 1 到 n 之间。但在最坏的情况下，我仍然无法得到O(n)。 另外，你不能粗暴地强制猜测数字，这是有限制的。

Answer 1

问题陈述有些地方含糊不清。我将给出我的假设，以及基于这些假设的答案，如果OP澄清了他们的问题并使我的假设无效，我将对此进行修改。

游戏规则：

• 存在一个数组

  M

  ，其中包含非递增顺序的正整数。
• 一次一个，按照数组顺序（非递增），玩家需要猜测当前的数字。
• 玩家知道他们试图猜测的数字是在 1 和他们找到的最后一个数字之间，或者最初是在 1 和 n 之间。
• 玩家每轮有 log(n) + 1 次猜测。
• 假设：对于每个错误的猜测，玩家都会得到正确答案的方向（无论他们的猜测太大还是太小）。
• 假设：|M| <= n.
• 目标：在 O(n) 时间内重新创建

  M

  。

我们将初始化 M[0] = n。

给定 M[i-1] = r 来猜测 M[i]：

• 我们最多有 log(n) 个猜测。如果我们使用这些来发现 M[i] 的值至少比 M[i-1] 小 log(n)，那么我们就可以实现在 O(n) 时间内完成此任务的目标。
• 我们只需要 log(n) 次猜测就能找到答案，但我们得到的是 log(n)+1。让我们用 +1 来找出答案是否在 M[i-1] 的 log(n) 之内。

给定 M[i-1] = r 的情况下猜测 M[i] 的方法：

• 猜测 1：M[i] = r - log(n)
• 如果猜测 1 大于正确答案，则在 1 和 r - log(n) - 1 之间使用二分查找。如果猜测 1 小于正确答案，则后续猜测应从 M[i-1] 开始并递减每次1个。

对于第二个项目符号，在这两种情况下，我们都可以在 log(n)+1 总猜测中确定 M[i]。但我们也保证 M[i] - M[i-1] >= 猜测次数 + 1。

因此，所有 M 的猜测总数最多为 |M| + n.假设|M| <= n (or really that |M| is O(n)), we have recreated M in O(n) time.