(待完成)如何快速找出两个递增数组合并后的中位数

---

参考资料：
https://blog.csdn.net/hhygcy/article/details/4584064

---

情况1：两个数组等长：

IMG_20180904_165103.jpg

具体代码：

#include<iostream>
using namespace std;
int res_a=-1,res_b=-1;
void find(int a[],int b[],int start_a,int end_a,int start_b,int end_b,int middle_a,int middle_b){
  // 假设a_len与b_len等长
  cout<<start_a<<" "<<end_a<<" "<<middle_a<<" "<<start_b<<" "<<end_b<<" "<<middle_b<<endl;
  // 考虑start==end的情况
  if(res_a!=-1&&res_b!=-1){
    cout<<"res:"<<min(res_a,res_b)<<endl;
    return;
  }
  else if(start_a==end_a){
    res_a=a[start_a];
    cout<<"a:"<<start_a<<endl;
  }
  else if(start_b==end_b){
    res_b=b[start_b];
    cout<<"b:"<<start_b<<endl;
  }

  // 对中位数的大小进行判断，然后执行不同递归。
  if(a[middle_a]==b[middle_b]){
    cout<<a[middle_a];
    return;
  }
  else if(a[middle_a]>b[middle_b]){
    if(middle_a==start_a){
      // 当start==middle而且middle-1的情况进行单独处置。
      find(a,b,start_a,middle_a,middle_b+1,end_b,start_a,(middle_b+1+end_b)/2);
      return;
    }
    else{
      find(a,b,start_a,middle_a-1,middle_b+1,end_b,(start_a+(middle_a-1))/2,(middle_b+1+end_b)/2);
    }
  }
  else{
    if(middle_b==start_b){
      find(a,b,middle_a+1,end_a,start_b,middle_b,(middle_a+1+end_a)/2,middle_b);
      return;
    }
    else{
      find(a,b,middle_a+1,end_a,start_b,middle_b-1,(middle_a+1+end_a)/2,(start_b+middle_b-1)/2);
      return;
    }
  }
  return;
}
void middle(int a[],int b[],int a_len,int b_len){
  find(a,b,0,a_len-1,0,b_len-1,(a_len-1)/2,(b_len-1)/2);
}
int main(){
  int a[]={0,1,2,3,4,5};
  int b[]={6,7,8,9,10,11};
  middle(a,b,6,6);
}

---

情况2：

假设偶数的时候中位数等于n/2n的数，或者n+1/2n+1的数。

---

情况3：

如果把中位数改为第k大的数怎么办？

例题：https://leetcode.com/problems/median-of-two-sorted-arrays/description/
解法参考: https://www.cnblogs.com/YaoDD/p/5205554.html

1）若a[k/2-1]==b[k/2-1]，则该值就是我们所要求的值，因为将a和b的前k/2个元素归并后就获得了a，b序列的前k个元素，并且a[k/2-1]和b[k/2-1]相等且在最末尾。

2）若a[k/2-1]<b[k/2-1]，则a的前k/2个元素中并不包含我们所求的第k小的元素，因此我们可以将其舍弃，进而递归求解剩下这些元素的第(k-k/2)小的元素。

3）若a[k/2-1]>b[k/2-1]，处理方法和情况2类似