（搜索已排序的紧凑链表）对于含n个元素的链表紧凑的维持在数组_

（搜索已排序的紧凑链表）对于含n个元素的链表紧凑的维持在数组的前n个位置，假设所有的关键字均不相同，且紧凑链表是已排序的，即对所有的i=1，2,...,n且 $next[i]\ne NIL$ ，有key[i]<key[next[i]]。又假设有一个变量L存放链表的首部元素的下标。在这些假设下，试说明可以利用下列随机算法在 $O(\sqrt{n})$ 的期望时间内搜索链表。

COMPACT-LIST-SEARCH(L,n,k)
1 i=L
2 while  and key[i]<k
3        j=RANDOM(1，n)
4        if key[i]<key[j] and  5           i=j
6           if key[i]==k
7                return i
8       i=next[i]
9 if i==NIL or key[i]>k
10   return NIL
11 esle return i

如果忽略过程中第3~7行，就得到一个普通的搜索已排序链表的算法，其中下标i依次指向链表的各个位置。当下标i越出表的末端或 $key[i]\geq k$ 时，搜索终止。在后一种情况中，如果key[i]=k，显然，我们已找到为k的关键字。但如果key[i]>k，则我们永远也找不到值为k的关键字，因而终止查找是正确的。

第3~7行意图向前跳至某个随机选择的位置j。当key[j]大于key[i]而不大于k时，这种跳跃是有益的。因为在这种情况下，j在链表中标识了一个正常搜索中i将要到达的位置。由于该链表是紧凑的，所以在1到n中任意选择一个j都会指向链表中的某个对象，而不会是自由表中的某个位置。

我们不直接分析COMPACT-LIST-SEARCH的性能，而是要分析一个相关的算法COMPACT-LIST-SEARCH'，该算法执行两个独立的循环。该算法增加了一个参数t，用来决定第一个循环迭代次数的上限。

COMPACT-LIST-SEARCH'(L,n,k,t)
1  i=L
2  for q=1 to t
3     j=RANDOM(1，n)
4        if key[i]<key[j] and  5           i=j
6           if key[i]==k
7                return i
8    while  and key[i]<k
9        i=next[i]
10  if i==NIL or key[i]>k
11   return NIL
12  esle return i

为了比较算法COMPACT-LIST-SEARCH(L,n,k)和COMPACT-LIST-SEARCH'(L,n,k,t)的执行过程，假定调用RANDOM(1,n)所返回的整数序列在两个算法中是一样的。

a.假设COMPACT-LIST-SEARCH(L,n,k)中第2~8行的while循环经过了t次迭代。论证COMPACT-LIST-SEARCH'(L,n,k,t)会返回同样的结果，且COMPACT-LIST-SEARCH'中的for 循环和while循环的迭代次数之和至少为t。

在COMPACT-LIST-SEARCH'(L,n,k,t)的调用中，设随机变量Xt描述了第2~7行的for循环经t次迭代后链表中从位置i到目标关键字k之间的距离（即通过了next指针链）。

b.论证COMPACT-LIST-SEARCH'(L,n,k,t)的期望运行时间为O(t+E[Xt])。

c.证明： $E[X_{t}]\leq \sum_{r=1}^{n}{(1-r/n)^{t}}$ 。