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

开始看算法导论，网上搜了一下这一题的思路，没有找到正确答案，都是简单的(1+n)/2。

因此自己动笔写了写，答案应该是(1-(1-p)^n)/p (p是概率，n是数组的长度)。

以下是证明过程与C语言程序验证：

IMG_0029(20180314-102808).jpg

过程中的难点就是等差等比数列的求和，网上搜下公式应该不难。

以下是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次下的试验平均结果。代入数字，与公式的答案相符。证明完毕。