bra*_*ter 3 arrays algorithm data-structures
给定一个数组,每个元素比其前一个元素多一个或一个.查找其中的一个元素.(优于O(n)方法)
我有一个解决方案,但我没有办法正式告诉它是否是正确的解决方案:
让我们假设我们必须找到n.
d元素分开和跳跃d元素d= 0是的,你的方法会奏效.
如果您只能在每个后续索引处增加/减少1,则索引处的值d不可能比距离d当前值的距离更近.所以你无法跳过目标值.并且,除非找到该值,否则距离将始终大于0,因此您将继续向右移动.因此,如果值存在,您将找到它.
不,你不能比O(n)最坏的情况做得更好.
考虑一个数组1,2,1,2,1,2,1,2,1,2,1,2,你正在寻找0.任何一个2都可以改为a,0而不必改变任何其他值,因此我们必须查看所有2的和有的n/2= O(n) 2.