在数组中搜索前一个元素的每个元素+1或-1的数字[关闭]

Question

整数数组包含一些元素，以使每个元素比其前一个元素多1个或小于1个。现在给了一个数字，我们需要确定该数字在数组中首次出现的索引。需要优化线性搜索。它不是功课。

Answer 1

我的算法是这样的：

1. p = 0
2. 如果（A [p] == x）则idx = p并且算法完成，否则转到下一步
3. 设置p + = | xA [p] |
4. 转到2。

说A [p]> x。然后，由于A项增加或减少1，因此idx至少可以确定与p的索引（A[p]-x）。A[p]<x的原理相同。

int p=0, idx=-1;
while (p<len && p>=0)
   if (A[p]==x)
       idx = p;
   else
       p+= abs(x-A[p]);

时间复杂度：最坏的情况是O（n）。我希望平均情况比O（n）好（我认为是O（logn），但不确定）。运行时间：在所有情况下，绝对比线性搜索好。