[数据结构与算法]两个有序序列的中位数

已知有两个等长的非降序序列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?感谢