分治法求中位数

两个有序序列,求中位数,要求两个序列有序的等长

如果两个有序序列的的中位数相同,那么这个数就是中位数

如果左序列的中位数大于右序列的中位数,那么舍弃左序列的后半部分,舍弃右序列的前半部分

如果左序列的中位数大雨右序列的中位数,那么舍弃左序列的前半部分,舍弃右序列的后半部分

原理:

如果a[midleft]>a[midright],则a[midleft]合并后在a[midright]右侧,那么在序列中偏右,那么中位数一定在[0-midleft],或者[midright-n]

        如果a[midleft]=a[midright],那么a[midright]的左侧必定小于a[midleft],a[midright]的右侧必定大于     a[midleft],则合并后右侧在midleft前面加一半,在midleft右边加一半,那么还是中位数

          同理a[midleft]<a[midright],同情况1

算法实现:

最后修改:2020 年 09 月 04 日 02 : 51 PM