arrays - 在数组中找到一个元素，其中每个元素都比其前一个元素大一或小一

Question

给定一个数组，每个元素都比它的前一个元素多一个或少一个。在其中找到一个元素。（优于 O(n) 方法）

我对此有一个解决方案，但我无法正式判断它是否是正确的解决方案：

假设我们必须找到 n。

• 从给定的索引，找到到 n 的距离；d = |a[0] - n|
• 所需的元素将至少是d分开的元素和跳跃d元素
• 重复上述直到d= 0

Answer 1

是的，你的方法会奏效。

如果您只能在每个后续索引处增加/减少 1，则索引处的值d不可能比d与当前值的距离更近。因此，您无法跳过目标值。而且，除非找到该值，否则距离将始终大于 0，因此您将继续向右移动。因此，如果该值存在，您就会找到它。

不，你不能比O(n)最坏的情况做得更好。

考虑一个数组1,2,1,2,1,2,1,2,1,2,1,2，您正在寻找0. 任何2' 都可以更改为 a0而无需更改任何其他值，因此我们必须查看所有2' 并且有n/2= O(n) 2。

Answer 2

预处理可以在这里提供帮助。以 O(n) 时间复杂度查找数组的最小和最大元素。如果要查询的元素介于数组的最小值和最大值之间，则该元素存在于数组中，否则该元素不存在于该数组中。因此任何查询都需要 O(1) 时间。如果多次查询该数组，则摊销时间复杂度将小于 O(n)。