线性搜索优化 - 减少计算次数

Question

我想知道 - 是否可以改进线性搜索算法（在数组上，而不是列表上），以便它可以完成大约一半的计算？

例如，这是基本的线性搜索算法：

i <- 1
while i<=length[a] && a[i]!=v
     do i <- i+1
if i>length[a]
     then return NIL
      else return i

现在，如果它被排序，我们可以使用二进制排序或使用上限函数来完成大约一半的计算，据我所知。但如果给定数组的算法未排序 - 我们可以进行大约一半的计算吗？

如果我计算正确，预期的计算次数是(n-1)(n+2)/2n，而最坏的情况是n-1

是否可以减少一半左右的计算次数？

注意：使用哨兵可能会有所改善，但仍然不会将其减少到大约一半的计算量

非常感谢您的帮助

Answer 1

首先，n/2仍然是O(n)。第二，如果搜索到的元素在一个数组中，并且数组中的所有数字都不相同（如果重复比较的次数更小），那么比较的次数：

1/(n-1)*1 + 1/(n-1)*2 +...+ 1/(n-1)*n-1 = 1/(n-1)*(1+2+...+n-1) = 1/n*(n*(n-1)/2) = (n-1)/2

但是如果搜索到的元素不在数组中，那么您需要使用数组中不同元素的数量除以所有可能元素的数量而不是 1/n 因子 objects/numbers。如果比值很小，很可能你需要遍历整个数组来检查它是否是一个数组，所以你需要几乎 n 次比较。如果从底层宇宙中提取的数组中的元素不均匀，那么分析可能会很复杂。

linear search optimization - cutting number of calculations