（参数传递代价）我们有一个假设——过程调用中的参数传递花费常量的时间，即使传递一个N个元素的数组也是如此。在大多数系统中，这个假设是成立的，因为传递的是指向数组的指针，而非数组本身。本题讨论三种参数传递策略：
1.数组通过指针来传递、时间=)
。
2.数组通过元素复制来传递。时间=)
，其中N是数组的规模。
3.传递数组时，只复制过程可能访问的子区域。若子数组A[p..q]被传递，则时间=)
。
a.考虑在有序数组中查找元素的递归二分查找。分别给出上述三种参数传递策略下，二分查找最坏情况运行时间的递归式，并给出递归式解的好的上界。令N为原问题的规模，n为子问题的规模。
b.对下面MERGE-SORT算法重做（a）。
MERG(A,p,q,r) n1 <-- q-p+1 n2 <-- r-q create arrays L[1...n1+1] and R[1...n2+1] for i<--1 to n1 do L[i] = A[p+i-1] for i<--i to n2 do R[i] = A[q+i] L[n1+1] = 极大值哨兵元素 R[n2+1] = 极大值哨兵元素 i<--1 j<--1 for k<-- p to r do if L[i] <= R[j] then A[k] = L[i] i++ else A[k] = R[j] j++ MERGE-SORT(A,p,r) if p<r then q<--(p+r)/2 MERGE-SORT(A,p,q) MERGE-SORT(A,q+1,r) MERGE(A,p,q,r)
