检查数字是否在数组中,复杂性最小

Question

给出一个数组,任何两个后续元素之间的距离是一(+1或-1).我们给出了一个数字.我们如何以最小的复杂度检查数字是否在数组中.

Answer 1

你可以做一些二进制搜索.

如果我们要查找的元素位于第一个和最后一个元素之间,我们知道元素出现在数组中,我们可以停止.

如果不是,请检查数组中可能出现的最小和最大可能值,方法是找出第一个和最后一个元素之间的差异,减去元素数量,将其除以2,然后从/减去/添加到最小值/最大值两个.

更明确地说:

temp = abs(arr[left] - arr[right]) - (left - right)
minPossible = min(arr[left], arr[right]) - 2*temp
maxPossible = max(arr[left], arr[right]) + 2*temp

递归重复,将数组分成两半(或按照Daniel的建议拆分).

为什么上面给出了最小/最大可能:

可以想象如下:你需要一些元素,这些元素等于左边和右边之间的差异,从一个到另一个.除此之外,对于每一步,你需要再次上下移动该步骤.

不幸的是,不低于O(n)最坏的情况.

这就是O(n)最坏情况不能被击败的原因:

(类似于大卫的证据).

示例输入= [1,0,1,0,1,0,1,0]

假设我们正在寻找2.

它显然不存在,但是如果0中的一个被改为2呢？我们需要检查每一个零点.一旦我们跳过一个,那个人就可以成为2.

因此,我们必须检查至少1/2的元素,因此它仍然是O(n/2)= O(n).

Answer 2

您可以使用以下算法保存检查某些(可能是大多数)元素.

如果您的数字是85并且数组的第一个数字是100,您可以跳过(15-1)= 14个数字(当然15是100和85之间的距离),因为它们最接近85可以是99,98 ,97,...,86.所以你只需检查第15个数字.如果该数字不是85,请继续重复相同的算法.这使您可以跳过数组,这仍然是O(N),但可能在时钟时间上比单独检查更快.

最糟糕的情况是:我正在寻找85.

• 第一个数字是86.我不能跳过任何数字因为(1-1)= 0而下一个数字很可能是85.
• 我检查下一个号码.它是87.啊,现在我可以跳过一个数字,因为(2-1)= 1; 我跳过的下一个号码可能是88或86,但从不85.
• 我检查另一个下一个号码,它是86.
• 一切都继续是相同的,因为阵列实际上是86,87,86,87,86,87,......所以我最终检查了所有的87,这几乎是数字的一半.

在我读到这个答案之前,我认为这是最佳算法.