Exercise

9.1-1

对所有的元素，两个一组进行比较，共需n-1次比较，可以构成一棵二叉树，最小的元素在树的根结点上，接下来，画出二叉树，可以很容易的看出共需lgn-1次比较，所以共需n+lgn-2次比较才可以找出第二小的元素。

9.1-2

略。

9.2-1

在randomized-select中，对于长度为0的数组，此时p=r，直接返回A[p],所以不会进行递归调用。

9.2-2

略。

9.2-3

RANDOMIZED-SELECT(A,p,r,i){
    while(true){
        if(p==r)
            return A[p];
        q=RANDOMIZED-PARTITION(A,p,r);
        k=q-p+1;
        if(i==k)
            return A[q];
        else if(i<k)
            q--;
        else{
            q++;
            i-=k;
        }
    }
}

9.2-4

每次都以最大的元素进行划分即可。

9.3-1

数学计算，根据书中例题仿照分析即可。

9.3-3

随机化

9.3-5

类似主元划分，只要把黑箱子输出的值作为主元划分去选择即可。

9.3-6

多重二分即可。

9.3-7

算出中位数，之后算出每一个数与中位数的差即可。

9.3-8

分别取两个数组的中位数进行比较，如果两个中位数相等，那么即为所求，否则，取中位数较小的一个的右边，取较大的一个的右边，直到就剩4个元素为止，这时候只要求这4个元素的中位数即可。

算法导论第九章习题答案（第三版） Introduction to Algorithm