求两个等长有序数组的中位数的logN算法 分治法

 #include <iostream> 
 using namespace std;  
  
 int findNthNumber(int a[], int b[], int n){  
  int l = 0, r = n -1;  
  int m;  
  while(l <= r){  
         m = (l + r) / 2;  
  if(m == n - 1 || a[m] < b[n - m -2]){  
  //此时比a[m]小的数最多只有n-2个，即a[m]不可能为第n小数，偏小更新左界 
             l = m + 1;  
         }  
  else if (a[m] < b [n - m - 1]){  
  //此时比a[m]小的数恰好有n-1个，a[m]就是第n小数，返回 
  return a[m];  
         }  
  else r = m - 1;//此时比a[m]小的数至少有n个，即a[m]不可能为第n小数，偏大更新右界 
     }  
  //中位数在b数组中的情况，和上面类似 
     l = 0, r = n -1;  
  while(l <= r){  
         m = (l + r) / 2;  
  if(m == n - 1 || b[m] < a[n - m -2]){  
             l = m + 1;  
         }  
  else if (b[m] < a [n - m - 1]){  
  return b[m];  
         }  
  else r = m - 1;  
     }  
 }  
  
 int main(){  
  int  a[] = {1, 3, 4, 9, 11, 20, 21};  
  int  b[] = {2, 7, 8, 10, 70, 76, 79};  
     cout<<findNthNumber(a, b, 7)<<endl;   
  return 0;  
 }  

 #include <iostream> 
 using namespace std;  
  
 int findNthNumber(int a[], int b[], int n){  
  int l = 0, r = n -1;  
  int m, tmp;  
  while(l <= r){  
         m = (l + r) / 2;  
         tmp = (a[m] < b [n - m - 2] ? b[n - m - 2] : a[m]);  
  //tmp取a[m]与b[n-m-2]中较大的一个，然后与a[m+1]和b[n-m-1]作比较 
  if(tmp > b [n - m - 1]){  
             r = m - 1;  
         }  
  else if(tmp > a [m + 1]){  
             l = m + 1;  
         }  
  else return tmp;  
     }  
 }  
  
 int main(){  
  int  a[] = {1, 3, 10, 11, 12, 20, 21};  
  int  b[] = {2, 7, 8, 9, 70, 76, 79};  
     cout<<findNthNumber(a, b, 7)<<endl;   
  return 0;  
 }