标签:中位数

求两个升序序列的中位数的最优算法

设计一个在时间和空间两方面都尽可能高效的算法,找出两个升序序列 A 和 B 的中位数(也就是两个序列合起来的中位数),最优算法思想如下: 设 A、B 的长度为 n,中位数分别为 a、b; 1)若 a=b,则 a 或 b 即为所求中位数,算法结束; 2)若 a<b,则舍弃 A 中较小的一半,同时舍弃序列 B 中较大的一半,要求两次舍弃的长度相等;   ……