algorithm - 线性搜索平均需要检查多少个元素？

Question

问题：考虑线性搜索。假设要搜索的元素同样可能是数组中的任何元素，平均需要检查输入序列的多少元素？

我该如何解决这个问题？我是否需要考虑元素不存在于序列中的情况？对于这种情况，需要检查所有 n 个元素。

总数 的案例是(n + 1)。因此平均没有。要检查的元素 = (1 + ... + n + n) / (n + 1). 这个答案正确吗？

Answer 1

区分元素在数组中（成功搜索）和不在数组中（搜索不成功）的两种情况。

对于成功的搜索，平均值为 (1 + 2 + ... + n) / n = (n + 1) / 2。

对于不成功的搜索，平均值仅为 n。

现在，总平均值取决于成功与不成功搜索的组合。例如，如果大多数搜索不成功，它将接近 n。如果所有搜索都成功（这似乎是问题的意思），则平均值为 (n + 1) / 2。

如果成功搜索的概率是 p，因此对于不成功的搜索 1-p，我们得到 p * (n+1) / 2 + (1-p) * n 的平均值。