算法导论 2.2-3 再次考虑线性查找问题

再次考虑线性查找问题（参见练习2.1-3）。假定要查找的元素等可能地为数组中的任意元素，平均需要检查输入序列的多少元素？最坏情况又如何呢？用Θ记号给出线性查找的平均情况和最坏情况运行时间。证明你的答案。

线性查找伪代码如下：

假定要查找的元素等可能的为数组中的任意元素，平均需要检查输入序列的元素个数为： 。将该式子进行运算可得 。

由此可得平均需要检测的输入序列元素个数为  。

在最坏情况下，要查找的元素应为数组的最后一个元素，这样一来需要查找的元素个数将始终为 n。

平均情况下，由于需要检测的元素个数为 ，这个结果可以用  表达，所以该情况下运行时间可以用Θ(n) 表示。

最坏情况下，检测元素个数为 n，该情况下运行时间可以用Θ(n) 表示。