数据结构之两条有序顺序表的中位数查找（方法介绍）

在学习数据结构时遇到一种玄而又玄的方法，这种方法似乎可以按着某种规律去理解，但是又摸不着他的最深层的原理。

题目描述：

　　有一条顺序表A{1，3，4，5，6，7，8}，他的中位数是5即为位置是 （长度L/2）+1，当长度为偶数的时候则直接为L/2。

而要求是给两条有序的顺序顺序表找出其中的中位数（及两个表中所有数的中位数）

　　解题方法：

　　一、当然，无论什么问题都有笨方法，可以将两个数组合并然后直接根据数组下标求出中位数，但是其浪费了大量的存储空间。

故不采取。

　　二、重点讲这种方法。

1. 分别求出两个线性表的的中位数分别为   a,b,当两个中位数相等时直接退出
2. 当a>b时，则将a所在的线性表中数较大的那一半去掉，然后将b在的线性表中数较小的那一半去掉，再各自求剩下数的中位数；　　
3. 当a<b时，则将a所在的线性表中数较小的那一半去掉，然后将b在的线性表中数较大的那一半去掉，再各自求剩下数的中位数；

依次重复上述三个步骤直到只剩下两个数则取其中较小的那个为两个顺序表的中位数。

　　至于解题的原理，恕在下理解不深，我就不能深入解释了。如若有能解惑的仁兄，麻烦留言相告。

数据结构之两条有序顺序表的中位数查找（方法介绍）

原文：https://www.cnblogs.com/withheart1202-never/p/13629870.html