在数组中查找一个元素，其中每个元素都比其前一个元素大或小1。

Question

给定一个数组，每个元素都比它前面的元素多一个或少一个。在其中找到一个元素（时间复杂度要小于O(n)）。

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

假设我们要查找n。

- 从给定的索引开始，找到到n的距离；d = |a[0] - n| - 所需元素至少与d个元素分开，并跳过d个元素 - 重复上述操作，直到d = 0

- brainydexter

---

请举一个这样的数组的例子。二分查找对此目的不够好吗？ - hgoebl

@hgoebl 不是，它只适用于排序后的数组，而 OP 指的是像 [2,3,2,1,2,3,4] 这样的数组。 - Alma Do

你的算法看起来很合乎逻辑。你想要一个算法正确性的证明吗？ - Abhishek Bansal

@AbhishekBansal：是的，听起来是正确的，但那只是一种直觉。你知道那感觉吧 :) 我只是想确保它确实是正确的。 - brainydexter

Answer 1

是的，你的方法可行。

如果你只能在后续索引处逐个增加/减少一个值，那么离当前值距离小于 d 的索引处的值不可能是距离为 d 的目标值。因此你无法跳过目标值。除非找到该值，否则距离将始终大于 0，因此你会继续向右移动。因此，如果该值存在，你会找到它。

不，最坏情况下你不能比 O(n) 更优。

考虑一个数组 1,2,1,2,1,2,1,2,1,2,1,2，你要查找的值是 0。任何一个 2 都可以更改为 0 而不必更改其他任何一个值，因此我们必须查看所有的 2，而有 n/2 = O(n) 个 2。

- Bernhard Barker

---

感谢@Dukeling的解释。 - brainydexter

Answer 2

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

- DevCoder

---

只有当多个查询经常超出数组范围时才会出现。 - Teepeemm