已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,AN−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数（A0为第1个数）。
输入格式:
输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。
输出格式:
在一行中输出两个输入序列的并集序列的中位数。
输入样例1:
5
1 3 5 7 9
2 3 4 5 6输入样例2:
6
-100 -10 1 1 1 1
-50 0 2 3 4 5输出样例2:
1题目中中位数的概念：对于有序序列A0,A1,⋯,AN−1，第一个数下标为0，最后一个数下标为N-1，故中位数的下标为（0+N-1）/2 =（N-1）/2，即A(N−1)/2,是第⌊(N+1)/2⌋个数（A0为第1个数）。（[N-1]/2+1）
第一次通过的时候，用c语言，使用的数组。
#include<stdio.h>
#include<stdlib.h>
int main()
{
int i,j,n;
scanf("%d",&n);
int *p = (int *)malloc(sizeof(int)*n);
int *q = (int *)malloc(sizeof(int)*n);
int *h = (int *)malloc(sizeof(int)*n);
for(i = 0;i < n;i++)
{
scanf("%d",&p[i]);
}
for(j = 0;j < n;j++)
{
scanf("%d",&q[j]);
}
i = 0;
j = 0;
int k = 0;
while(k < n)
{
if(p[i] < q[j])
{
h[k++] = p[i++];
}
else
{
h[k++] = q[j++];
}
}
printf("%d",h[n -1]);
free(p);
free(q);
free(h);
return 0;
}输出中位数下标的确定：讲2N个元素存入数组h中后，元素按A0,A1....A(2N-1)存储，由上中位数的分析，要输出的中位数下标为（2N-1）/2即N-1，输出h(N-1)即可。
可采用二分查找的方法解答本题：
需要注意的为，舍弃某一数列的前半部分应与舍弃的另一数列前半部分个数相等。具体操作为：若要保留的是数组前半部分，则正常保留；若要保留的是数组的后半部分，则分两种情况（1）数组元素个数为奇数，则正常保留（2）数组元素个数为偶数，则需要少保留一位，即low = mid+1。
判断数组个数奇偶的方法：（low+high）/2 == 0 为奇，结果为1则为偶。原因为：若数组个数为奇数，则数组两端的元素下标应为同奇偶（345 3和5同为奇|234 2和4同为偶）同奇偶都两数相加均为偶数，故除以2没有余数；若数组个数为偶数，则数组两端下标一定奇偶性不相同，和必定为奇数，故除以2有余数。
#include<stdio.h>
int searchMid(int p[],int q[],int n){
int low1 = 0,high1 = n-1,low2 = 0,high2 = n-1;
while(low1 < high1 && low2 < high2){
int mid1 = (low1+high1)/2;
int mid2 = (low2+high2)/2;
if(p[mid1] == q[mid2]){
return p[mid1];
}
else{
if(p[mid1] < q[mid2]){
if((low1+high1)%2 == 0){
low1 = mid1;
}
else{
low1 = mid1+1;
}
high2 = mid2;
}
else{
if((low2+high2)%2 == 0){
low2 = mid2;
}
else{
low2 = mid2+1;
}
high1 = mid1;
}
}
}
if(p[low1]<q[low2]){
return p[low1];
}
else{
return q[low2];
}
}
int main(void){
int n,i;
scanf("%d",&n);
int *p = malloc(sizeof(int)*n);
int *q = malloc(sizeof(int)*n);
for(i = 0;i < n;i++){
scanf("%d",&p[i]);
}
for(i = 0;i < n;i++){
scanf("%d",&q[i]);
}
int x;
x = searchMid(p,q,n);
printf("%d",x);
free(p);
free(q);
return 0;
}时间复杂度缩小为logn,空间复杂度为1
代码及思路参考了
设计一个算法求给定的两个有序序列的中位数 （分治算法）_＃两个西柚-CSDN博客_两个有序序列的中位数
PTA：两个有序序列的中位数（二分法）_马可仕马可仕的博客-CSDN博客
两篇博客，感谢。
C++提供了sort排序函数，在本题直接运用很方便。
关于sort函数：
sort函数用于C++中，对给定区间所有元素进行排序，默认为升序，也可进行降序排序。sort函数进行排序的时间复杂度为n*log2n，比冒泡之类的排序算法效率要高，sort函数包含在头文件为#include的c++标准库中。
语法：sort(start,end,cmp)
start表示要排序数组的起始地址；
end表示数组结束地址的下一位；
cmp用于规定排序的方法，可不填，默认升序。
注意C++中引用的用法，在堆区开辟内存，手动开辟，手动释放。
利用new创建的数据，会返回该数据对应的类型的指针
数组释放方式：delete[] 数组名
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int *a = new int[2*n];
for(int i=0; i<n*2; i++)
cin>>a[i];
sort(a,a+2*n);
cout<<a[n-1]<<endl;
delete[] a;
return 0;
}本段代码参考了
https://blog.csdn.net/qq_45745322/article/details/108940879 感谢