（查找一个无序数组）本题将分析三个算法，它们在一个包含n个元素的无序数组A中查找一个值x。
考虑如下的随机策略：随机挑选A中的一个下标i。如果A[i]=x，则终止；否则，继续挑选A中一个新的随机下标。重复随机挑选下标，直到找到一个下标j，使A[j]=x，或者直到我们已检查过A中的每一个元素。注意，我们每次都是从全部下标的集合中挑选，于是可能会不止一次地检查某个元素。
a.请写出过程RANDOM-SEARCH的伪代码来实现上述策略。确保当A中所有下标都被挑选过时，你的算法应该停止。
b.假定恰好有一个下标i使得A[i]=x，在我们找到x和RANDOM-SEARCH结束之前，必须挑选A下标的数目期望是多少？
c.假设有
个下标i使得A[i]=x，推广你对（b）部分的解答。在找到x或RANDOM-SEARCH结束之前，必须挑选A的下标的数目期望是多少？你的答案应该是n和k的函数。
d.假设没有下标i使得A[i]=x，在检查完A的所有元素或RANDOM-SEARCH结束之前，我们必须挑选A的下标的数目期望是多少？
现在考虑一个确定性的线性查找算法，我们称之为DETERMINISTIC-SEARCH。具体地说，这个算法在A中顺序查找x，考虑A[1],A[2],A[3],...,A[n]，直到找到A[i]=x，或者到达数组的末尾。假设输入数组的所有排列都是都能可能的。
e.假设恰好有一个下标i使得A[i]=x，DETERMINISTIC-SEARCH平均情形的运行时间是多少？DETERMINISTIC-SEARCH最坏情形的运行时间又是多少？
f.假设有个下标i使得A[i]=x，推广你对（e）部分的解答，DETERMINISTIC-SEARCH平均情形的运行时间是多少？DETERMINISTIC-SEARCH最坏情形的运行时间又是多少？你的答案应该是n和k的函数。
g.假设没有下标i使得A[i]=x。DETERMINISTIC-SEARCH平均情形的运行时间是多少？DETERMINISTIC-SEARCH最坏情形的运行时间又是多少？
最后考虑一个随机算法SCRAMBLE-SEARCH，它先将输入数组随机变换排列，然后在排列变换后的数组上，运行上面的确定性线性查找算法。
h.设k是满足A[i]=x的下标的数目，请给出在k=0和k=1情况下，算法SCRAMBLE-SEARCH最坏情形的运行时间和运行时间期望。推广你对解答以处理的情况。
i.你将会使用3种查找算法中的哪一个？解释你的答案。
