PROSAGA码农传奇-C/C++-二进制搜索修改

<div class =“post-text”itemprop =“text”>
  
    你无法找到一个有效的解决方案（效率意味着没有查看所有数字，O（n）），因为你不能通过查看少于全部来总结你的数字。例如，如果你只看每一个数字（仍然是O（n）但更好的因素），你会错过这样的双跳：
     <code>
 1 5 3
 </code>
    。您可以而且必须查看每个数字并将其与其邻居进行比较。您可以分割工作负载并使用多核方法，但这就是它。
  
  
    的
      更新
    </强>
  
  
    如果您有特殊情况，列表中只有一个跳转，其余的都已排序（例如。
     <code>
 1 2 3 7 8 9
 </code>
    你可以相当有效地找到这种跳跃。您不能使用vanilla二分查找，因为列表可能没有完全排序，您不知道您正在搜索的是哪个数字，但您可以使用指数搜索的缩写，它具有一些相似之处。
  
  
    我们需要以下假设才能使用此算法：
  
  <UL>
    <LI>
      只有一次跳转（我忽略了“环绕跳转”，因为它在技术上不属于任何后续元素）
    </LI>
    <LI>
      该列表以其他方式排序，并且严格单调递增
    </LI>
  </UL>
  
    有了这些假设，我们现在基本上是在寻找单调性的中断。这意味着我们正在搜索2个元素和b之间有n个元素但不满足的情况
     <code>
 b = a + n
 </code>
    。如果两个元素之间没有跳转，则必须为true。现在你只需要找到不能以非线性方式实现这一点的元素，因此采用指数方法。这个伪代码可能是这样一种算法：
  
   <pre>
 <code>
 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

</code>
 </pre>
</DIV>