求两个有序数组的中位数(等长)

秒速五厘米 2021-10-13 15:42 344阅读 0赞

**1.        算法要求**

一个长度为L（L≥1）的升序序列S，处在第L / 2（若为小数则去掉小数后加1）个位置的数称为S 的中位数。例如，若序列S1=（11,13,15,17,19），则S1 的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=（2,4,6,8,20），则S1 和S2 的中位数是11。现在有两个等长升序序列A 和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数。

**2.        算法思想**

分别求出序列A 和B 的中位数，设为a 和b，求序列A 和B 的中位数过程如下：

1）若a=b，则a 或b 即为所求中位数，算法结束。

2）若a<b，则舍弃序列A 中较小的一半，同时舍弃序列B 中较大的一半,要求舍弃的长度相等；

3）若a>b，则舍弃序列A 中较大的一半，同时舍弃序列B 中较小的一半，要求舍弃的长度相等；

在保留的两个升序序列中，重复过程1）、2）、3），直到两个序列中只含一个元素时为止，较小者即为所求的中位数。

**3.        算法实现**

int M_Search(int A[], int B[], int n) 
    {
    	int start1 = 0, end1 = n - 1, m1, start2 = 0, end2 = n - 1, m2;
    	//分别表示序列A和B的首位数、末位数和中位数
    
    	while (start1 != end1 || start2 != end2)
    	{
    		m1 = (start1 + end1) / 2;
    		m2 = (start2 + end2) / 2;
    		if (A[m1] == B[m2])
    			return A[m1];   //满足条件 1)
    
    		if (A[m1]<B[m2]) // 满足条件 2)
    		{  
    			if ((start1 + end1) % 2 == 0)  //若元素个数为奇数
    			{  
    				start1 = m1;  //舍弃A中间点以前的部分且保留中间点
    				end2 = m2;  //舍弃B中间点以后的部分且保留中间点
    			}
    			else				//元素个数为偶数
    			{ 
    				start1 = m1 + 1;  //舍弃A中间点及中间点以前部分
    				end2 = m2;  //舍弃B中间点以后部分且保留中间点
    			}
    		}
    		else
    		{  //满足条件3)
    			if ((start2 + end2) % 2 == 0)   //若元素个数为奇数
    			{ 
    				end1 = m1;    //舍弃A中间点以后的部分且保留中间点
    				start2 = m2;    //舍弃B中间点以前的部分且保留中间点
    			}
    			else     //元素个数为偶数
    			{  
    				end1 = m1;    //舍弃A中间点以后部分且保留中间点
    				start2 = m2 + 1;    //舍弃B中间点及中间点以前部分
    			}
    		}
    	}
    	return  A[start1]<B[start2] ? A[start1] : B[start2];
    }

参考：https://blog.csdn.net/juliet0727/article/details/88380866

转自：  
https://blog.csdn.net/yanyangjuhua/article/details/78825603

## 详细算法描述：     ① 输入两个长度自定且等长的数组，然后对他们进行赋值。算法的思路是分别取他们的中位数进行比较，假设两个数组如下：  <table>   <tbody>    <tr>     <td> <p>1</p> </td>     <td> <p>3</p> </td>     <td> <p>5</p> </td>     <td> <p>7</p> </td>     <td> <p>9</p> </td>    </tr>    <tr>     <td> <p>2</p> </td>     <td> <p>3</p> </td>     <td> <p>4</p> </td>     <td> <p>5</p> </td>     <td> <p>6</p> </td>    </tr>   </tbody>  </table>  上面数组的中位数是比下面数组的中位数大的，接下来的操作就是取大中位数的左边（包括中位数），取小中位数的右边（包括中位数）。  <table>   <tbody>    <tr>     <td> <p>1</p> </td>     <td> <p>3</p> </td>     <td> <p>5</p> </td>    </tr>    <tr>     <td> <p>4</p> </td>     <td> <p>5</p> </td>     <td> <p>6</p> </td>    </tr>   </tbody>  </table>  再次重复以上操作，最后有  <table>   <tbody>    <tr>     <td> <p>3</p> </td>     <td> <p>5</p> </td>    </tr>    <tr>     <td> <p>4</p> </td>     <td> <p>5</p> </td>    </tr>   </tbody>  </table>  接下来已经不能再分别取他们的中位数缩小范围了，所以对两个数组进行比较。取数组的首位进行比较，如上即是3和4进行比较，若是哪边比较小就取它的下一位进行比较。过程就是3和4比（3比4小，所以下标加1）→5和4比（4比5小，所以得到中位数为4）→中位数为4。  这是当数组为奇数长度的情况，若是数组长度为1，或者是数组长度为偶数，要再次进行讨论。  ② 当数组长度为1时，比较两个数，谁比较小谁就是中位数。  ③ 当数组长度为偶数时，  <table>   <tbody>    <tr>     <td>      <div>       <p>-100</p>      </div> </td>     <td> <p>-10</p> </td>     <td> <p>1</p> </td>     <td> <p>1</p> </td>     <td> <p>1</p> </td>     <td> <p>1</p> </td>    </tr>    <tr>     <td> <p>-50</p> </td>     <td> <p>0</p> </td>     <td> <p>2</p> </td>     <td> <p>3</p> </td>     <td> <p>4</p> </td>     <td> <p>5</p> </td>    </tr>   </tbody>  </table>  在第一步，取数组的中位数时候，若是按照奇数的方法，我们会发现，最后取出来的两个数组不是等长的，这样的话就会对我们的实际结果造成影响。如上，我们可以一个数组取第三个数，一个数组取第四个数这样进行比较，这样接下来得到的数组都是等长的。接下来步骤和奇数数组一样。  ④ 在这里，偶数数组这样的取法原因是，我们每次取新数组出来，只要两个数组的长度和加起来是原来数组的一半或者大于一半，我们就可以保证中位数一直在我们取出来的新数组里面，不会出现中位数丢失的情况。            算法时间及空间复杂度分析：     时间复杂度：每一次调用的过程为判断余下数组长度是否大于2，接下来判断数组个数是奇数个还是偶数个，最后判断两个数组的中位数谁大谁小。所以t(n) = O(1)+O(1)+O(1)。总共执行次数为logn次。在主函数中，执行的语句为创建两个数组还有数组左右下标等变量，和为数组赋值。所以总的时间复杂度为T(n) = logn\*t(n)+O(n)+O(1) = O(logn)。     空间复杂度：算法中辅助空间并不随着数组长度n而线性增大，所以空间复杂度为O(1)。      ##