一个长度为L (L ≥ 1)的升序序列S，处在第[L/2]个位置的数称为S的中位数。例如，若序列S1=(11, 13, 15, 17, 19)，则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2= (2, 4, 6, 8, 20)，则S1和S2的中位数是11。
给出两个有序序列A和B，它们的长度相等。设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。
单测试用例。
第一行是L，表示两个有序序列A和B的长度。1 < L ≤ 1000000
第二行是序列A，空格分隔的L个整数。
第三行是序列B，空格分隔的L个整数。
输出一个整数，A和B的中位数。无需换行。
5
11 13 15 17 19
2 4 6 8 20
11
#include<bits/stdc++.h> const int maxn = 1e6+10; using namespace std; int a[maxn],b[maxn]; int solve(int l1,int r1,int l2,int r2){ int m1=(l1+r1)/2,m2=(l2+r2)/2; if(l1==r1||l2==r2)return min(a[m1],b[m2]); if(a[m1]==b[m2])return a[m1]; if(a[m1]>b[m2]){ if((r1-l1+1)%2) return solve(l1,m1,m2,r2); else return solve(l1,m1,m2+1,r2); } else{ if((r1-l1+1)%2) return solve(m1,r1,l2,m2); return solve(m1,r1,l2,m2+1); } } int main() { int n;cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>b[i]; printf("%d\n",solve(0,n-1,0,n-1)); }
原文：https://www.cnblogs.com/JAJA-Xin/p/14085351.html