以下是引用teng_t1986在2006-5-19 20:54:00的发言： 我认为不要建堆，可以先比较两个数组的中间位置的值，根据比较结果把一个指针右移另一个左移（即始终保证一个指针右半边长度加另一个指针左半边长度和为n），直到两指针值相等或与前一次寻找位置相邻是算法结束。 因为过程为binary search，所以时间代价为O(logN)，对吗？

Say the two arrays are sorted and increasing, namely A and B.
It is easy to find the median of each array in O(1) time.
Assume the median of array A is m and the median of array B is n.
Then,
1' If m=n, then clearly the median after merging is also m, the algorithm holds.
2' If m<n, then reserve the half of sequence A in which all numbers are greater than
   m, also reserve the half of sequence B in which all numbers are smaller than n.
   Run the algorithm on the two new arrays.
3' If m>n, then reserve the half of sequence A in which all numbers are smaller than
   m, also reserve the half of sequence B in which all numbers are larger than n.
   Run the algorithm on the two new arrays.

Time complexity: O(logn)

#include <iostream>
#include <time.h>
using namespace std;

int find_nth(int A[],int B[], int A_start, int A_end, int B_start, int B_end, int n) //从 A[start]..A[end],B[start]...B[end] 中找出第 n 小的数。
{
 if(A_end<A_start)
  return B[B_start+n-1];
 else if(B_end<B_start)
  return A[A_start+n-1];
 else if (n == 1)
  return A[A_start]<=B[B_start]?A[A_start]:B[B_start];  //当 n = 1 时，第 n 小的数就是两个数中较小的那个。
 else if(n == 2)
 {
  if(A[A_start]<=B[B_start])
   return find_nth(A,B,A_start+1,A_end,B_start,B_end,n-1);
  else
   return find_nth(A,B,A_start,A_end,B_start+1,B_end,n-1);
 }
 else
 {
  int A_mid, B_mid;
  A_mid = A_start + (n-1)/2;
  B_mid = B_start + (n-1)/2;
  if (A[A_mid]==B[B_mid])
   return A[A_mid];
  else if (A[A_mid]<B[B_mid])  //这时，A[A_start]...A[A_mid]一定比"第 n 小的数"小，B[B_mid+1]...B[B_end]一定比"第 n 小的数"大，不必再考虑。
   return find_nth(A, B, A_mid, A_end, B_start, B_mid, n - (A_mid - A_start));
  else
   return find_nth(A, B, A_start, A_mid, B_mid, B_end, n - (B_mid - B_start));
 }
}

void insertionSort(int X[], int start, int end)
{
 int i,j,temp;
 for(i = start; i<=end; i++)
 {
  temp = X[i];
  for(j=i-1; j>=start && X[j]>temp; j--)
   X[j+1]=X[j];
  X[j+1]=temp;
 }
}

void main()
{
 const int k=4;
 int A[k],B[k],i;
 srand( (unsigned)time( NULL ) );
 for(i=0;i<k;i++)
 {
  A[i]=rand();
  B[i]=rand();
 }
 insertionSort(A,0,k-1);
 insertionSort(B,0,k-1);
 cout<<"find_nth(A,B,0,"<<k-1<<",0,"<<k-1<<","<<k<<") = "<<find_nth(A,B,0,k-1,0,k-1,k)<<endl;

 //下面将A、B归并到数组C中，并直接输出C[k-1]，作为对照。 
 int C[2*k],s,t;
 s=0;
 t=0;
 for(i=0;s<k&&t<k;i++)
 {
  if(A[s]<=B[t])
   C[i]=A[s++];
  else
   C[i]=B[t++];
 }
 while(s<k)
 {
  C[i++]=A[s++];
 }
 while(t<k)
 {
  C[i++]=B[t++];
 }
 cout<<"C["<<k-1<<"] = "<<C[k-1]<<endl;
}

btw：考试时，我这道题做了1个多小时，当时急得满头大汗。我一直在寻找while中mid,right,left的关系，却从未想过用递归。而且因为这道题，我的整个考试时间全乱了，后面的os部分写的飞快，最后也没有检查....其实今年就两道难题——还有os那道作业题，我记得题目说“CPU可以抢占”，不知道是当时太紧张看错了还是确实如此，如果CPU可以抢占，那么最高相应比就需要列很多方程，也会产生抖动——除此之外，都是中等或以下的题，可是今年能考130左右的很少，估计都是背着两道题折腾的吧。

作业    进入时间    估计运行时间(分钟)

JOB1    8:00        120

JOB2    8:50        30

JOB3    9:00        10

JOB4    9:50        20

系统采用最高响应比优先（HRN）调度算法，采用多道程序设计思想，CPU可以抢占，问执行结果。
我对这道题型的回忆就是这样，最主要的问题就是CPU可以抢占

这里对收容一词作一点解释：北大的教材对收容的观点是作业的提交过程所需的时间是可以忽略不计的，一个作业到达时间即表示其被收容完毕的时间，处于收容态的某个作业一旦满足调度算法，就可以被调度，即一个作业被不被调度只于其是否被收容有关。（而其他教材，如清华的教材对收容的理解为：一批作业中的最后一个到达后之前的作业才全部收容完毕，即调度算法与所有作业的到达时间都有关系。这两种思想在做题时有时候会得到完全不同的答案）

对本题，就是说一个作业被调度取决于它到达的时间和是否满足调度算法。可以认为到达的作业都在输入井中，可以随时被调度。

以下是引用Logician在2006-5-22 21:49:00的发言： 作业调度不同于进程调度，作业一旦调入系统，在执行完之前是不会被换出的。抢占只是针对进程而言的吧？

我也看了下那本习题集，就是这题，花了我15分钟哦

 int dist=n/4;

 while(dist>1){

  if(A[pa]==B[pb]){
   return A[pa];
  }

  if(A[pa]<B[pb]){
   pa+=dist;
   pb-=dist;
  }else{
   pa-=dist;
   pb+=dist;
  }

  dist/=2;
 }
 return A[pa];
}//在vc6.0下编译通过。
可惜还有点小缺憾，不过可以用引用返回两个中值（即A、B中值不等的情况）

望高人指教！！

附件里是其它研友整理出来的专业课试题：

今年的“数学基础”试题我没有见到过系统的回忆和整理。

再等两、三个月，应该北大就会开始卖了。

哪儿错了啊？望指出。

对……我dist变量用的太草率了，边界没处理好……sigh，谢谢高人！
突然发现：在n<4的情况下恐怕要另行考虑（n==4是可以把while循环条件改为dist>=1），也就是要考虑n=2、n=3两种情况，对不起我太草率了……
莫非要硬性的加两行判断语句？n=2、3两种情况下似乎我的算法不适用呀……

 int dist=n/4;
 if(dist==0)dist=1;

 while(dist>=1){

  if(A[pa]==B[pb]){
   return A[pa];
  }

  if(A[pa]<B[pb]){
   pa+=dist;
   pb-=dist;
  }else{
   pa-=dist;
   pb+=dist;
  }

  dist/=2;
 }

 return A[pa];
}

不过n=2是还是不行（还没习惯在电脑面前思考:<），比如说A=1,3，B=2,3，一上来pa==pb==A[1]，于是便返回3…………55555555555555555
我在想想吧……

没关系，你已经写的不错了，今年那些考上的同学多数也没有作出这道题

不过我刚刚找了一下，题目好像是只要求写出算法思想，不要写代码吗？

我会努力找出不要硬性讨论的算法的……

另外，指定习题集的7.17题，已知数组中只有0，1，2三个值，要求在O(logn)时间内排序，这题正确吗？我觉得就是荷兰国旗问题，至少也要用O(n)一次遍历呀，还望高人指教（最好能给出O(logn)的代码）。

基于比较的排序算法上面已经给出了时间下限，若这道题有解，肯定不是基于比较的排序

不基于比较的排序比较适于这题的是桶排序，时间复杂为O（n+3）=.O(n)

看起来不像是出错了，而只有不看一些单元才能满足条件，但是究竟满足什么样条件的单元可以不看呢？？我感觉题目少条件，例如n=3时，若0，1，2都出现1次，则第三个单元是可以不看的。一般的情况就不知道了。。

这是《算法导论》上的课后习题，我当时看了就想出这么个算法。

  领教领教！
    我看到这道题是一点思路都没有，汗颜。。。。