二进制搜索修改

Question

我一直试图解决以下问题。我有一系列正整数，可能很长（数百万元素）。此序列可以在元素值中包含“跳转”。上述跳转意味着两个连续元素彼此相差超过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 2 3 7 8 9），您可以相当有效地找到此跳转。您不能使用vanilla二分查找，因为列表可能没有完全排序，您不知道您正在搜索的是哪个数字，但您可以使用指数搜索的缩写，它具有一些相似之处。

我们需要以下假设才能使用此算法：

• 只有一次跳转（我忽略了“环绕跳转”，因为它在技术上不属于任何后续元素）
• 该列表以其他方式排序，并且严格单调递增

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

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