分治法找两数组的中值

来源：百度知道 编辑：UC知道 时间：2024/06/17 19:05:12
设X[1..n]和Y[1..n]是两个有序数组，试设计运行时间为O(1b n)的算法，找出在数组X和Y中的2n个元素的中值。
请给出完整的程序。

这个就在教科书上阿。参考算法导论
很长的哦：
C#的，这个是计算第K个数的，令K=n/2就行了

using System;
using System.Collections;
using NUnit.Framework;
using Algorithm.Test;

namespace Algorithm.Select
{
/// <summary>
/// Kth_Samllest_Selection 的摘要说明。
/// </summary>
public class Kth_Samllest_Selection
{
ArrayList m_al;
ArrayList m_MedianAl;
ArrayList m_S1;
ArrayList m_S2;

int m_K;
public Kth_Samllest_Selection(ArrayList al,int K)
{
m_al = al;
m_K = K;
m_MedianAl = new ArrayList(al.Count/5+1);
m_S1 = new ArrayList(al.Count/2);
m_S2 = new ArrayList(al.Count/2);
}
/// <summary>
/// 执行操作
/// </summary>
/// <returns>第K个数的大小</returns>
public int Do()
{

if(m_al.Count<=5)
{
m_al.Sort();
return ((ComparableObject)m_al[m_K-1]).Valu