二分查找修改

Question

我一直在尝试解决以下问题。我有一系列积极的可以很长的整数（数百万个元素）。这个序列可以在元素值中包含 "jumps"。前面提到的跳跃表示两个连续元素彼此相差超过 1。

示例 01:

1 2 3 4 5 6 7 0

在上面提到的例子中，跳转发生在 7 和 0 之间。

我一直在寻找一些有效的算法（从时间的角度来看）找到发生此跳跃的位置。这个问题很复杂事实上，可能存在两个跳跃和其中一个跳跃的情况是我正在寻找的跳跃，另一个是我正在寻找的环绕我不是在寻找。

示例 02:

9 1 2 3 4 6 7 8

这里 9 和 1 之间的第一个跳跃是环绕。第二跳之间 4和6是我要找的跳跃。

我的想法是以某种方式修改二分搜索算法，但由于存在环绕，我不确定是否可行。值得一提的是，最多只能发生两次跳跃，并且在这些跳跃之间对元素进行排序。有人知道吗？在此先感谢您的任何建议。

Answer 1

您无法找到有效的解决方案（有效意味着不查看所有数字，O(n)），因为您无法通过查看少于所有数字来得出关于您的数字的任何结论。例如，如果你只查看每隔一个数字（仍然是 O(n) 但更好的因子），你会错过像这样的双跳：1 5 3。您可以而且必须查看每一个数字并将其与它的邻居进行比较。您可以拆分工作负载并使用多核方法，仅此而已。

更新

如果您遇到特殊情况，即您的列表中只有 1 个跳转而其余的已排序（例如 1 2 3 7 8 9），您可以相当有效地找到此跳转。您不能使用 vanilla 二进制搜索，因为列表可能未完全排序并且您不知道要搜索的数字，但您可以使用指数搜索的缩写，它有一些相似之处。

我们需要以下假设才能使该算法起作用：

只有 1 次跳跃（我忽略 "wrap around jump" 因为它在技术上不在任何后续元素之间）
列表以其他方式排序并且严格单调递增

有了这些假设，我们现在基本上是在寻找单调性的中断。这意味着我们正在搜索 2 个元素和 b 之间有 n 个元素但不满足 b = a + n 的情况。如果两个元素之间没有跳转，则这必须为真。现在您只需要找到不以非线性方式满足此要求的元素，因此采用指数方法。这个伪代码可能是这样一个算法：

let numbers be an array of length n fulfilling our assumptions

start = 0
stepsize = 1
while (start < n-1)
    while (start + stepsize > n)
        stepsize -= 1
    stop = start + stepsize
    while (numbers[stop] != numbers[start] + stepsize)
        // the number must be between start and stop
        if(stepsize == 1)
            // congratiulations the jump is at start to start + 1
            return start
        else
            stepsize /= 2
    start += stepsize
    stepsize *= 2

no jump found

二分查找修改

Binary search modification

c

binary-search