0001 template <typename T> // S1[lo1, lo1 + n)和S2[lo2, lo2 + n)分别有序,n > 0,数据项可能重复 0002 T median( Vector<T>& S1, Rank lo1, Vector<T>& S2, Rank lo2, Rank n ) { //中位数算法(高效版) 0003 if ( n < 3 ) return trivialMedian( S1, lo1, n, S2, lo2, n ); //递归基 0004 Rank mi1 = lo1 + n / 2, mi2 = lo2 + ( n - 1 ) / 2; //长度(接近)减半 0005 if ( S1[mi1] < S2[mi2] ) 0006 return median ( S1, mi1, S2, lo2, n + lo1 - mi1 ); //取S1右半、S2左半 0007 else if ( S1[mi1] > S2[mi2] ) 0008 return median ( S1, lo1, S2, mi2, n + lo2 - mi2 ); //取S1左半、S2右半 0009 else 0010 return S1[mi1]; 0011 }