题目是：再次考虑线性查找问题（参见联系2.1-3）。假定要查找的元素等可能地为数组中地任意元素，平均需要检查输入序列地多少元素？最坏情况又如何呢？用θ记号给出线性朝朝地平均情况和最坏情况地运行时间。证明你的答案。
以下是证明过程与C语言程序验证：
过程中的难点就是等差等比数列的求和，网上搜下公式应该不难。
以下是C语言代码的验证：
````
#include
#include
#include
int main()
{
int v = 23; //v为某个值
int count = 50000; //样本测试的次数
int size = 10; //数组的大小
double p = 0.2; //是v的概率
int h;
double sumIndex = 0;
int arr[size]; //定义数组
srand((unsigned)time(NULL));
for (int k = 0; k < count; k++)
{
for (int i = 0; i < size; i++)
{
if ((double)rand() / RAND_MAX <= p)
{
arr[i] = v;
}
else
{
arr[i] = 1;
}
}
for (int j = 0; j < size; j++)
{
if (arr[j] == v || (j == (size - 1) && arr[j] != v))
{
v = 0;
sumIndex += (j + 1);
break;
}
}
v = 23;
}
printf("%f", (double)(sumIndex / count));
return 0;
}
````
4.459680是大小为10的数组在5w次下的试验平均结果。代入数字，与公式的答案相符。证明完毕。
