在数组中搜索数字与每个元素+1或preceding元-1 [英] Searching in an array for numbers with each element +1 or -1 of preceding element
问题描述
整数数组包含元素，每个元素比它的preceding元1多跌少。现在，我们给出了一些，我们需要确定阵列中该号码的第一个出现的索引。 需要优化线性搜索。它不是功课。
An array of integers contains elements such that each element is 1 more or less than its preceding element. Now we are given a number, we need to determine the index of that number's first occurrence in the array. Need to optimize linear search. Its not homework.
推荐答案
我的算法是这样的：
- P = 0
- 如果（A [P] == X）则IDX = p和算法，否则完成转到下一步
- 设置P + = | X-A [P] |
- 转到2。
说A [P]>的X.然后，因为A项增加或减少1，IDX是肯定的，至少（A [P] - x）的指数离页。同样的原则也适用于A [P]＆LT;的X.
say A[p] > x. Then, since A items increase or decrease by 1, idx is for sure at least (A[p] - x) index away from p. Same principle goes for 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（log n）的，但不知道这件事）。 运行时间：绝对比所有案件线性搜索，更好的
Time complexity: The worst case would be O(n). I expect the average case to be better than O(n) ( I think it's O(log n) but not sure about it). Running time: Definitely better than linear search for all cases.
这篇关于在数组中搜索数字与每个元素+1或preceding元-1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
