减治算法之寻觅两个递增序列的中位数

减治算法之寻找两个递增序列的中位数

一、问题描述

寻找两个递增序列的中位数。

本算法中只能解决两个序列长度规模相等的问题，若两个序列长度规模不相等，则可以先做合并（leetcode：Merge Sorted Array 【Java】）后再寻找中位数。

二、问题分析

分别计算序列A，B的中位数a，b

比较中位数a，b，会出现以下三种请款

（1）a = b，直接返回结果a

（2）a < b，两个序列的中位数只能出现在[a，b)，在序列中A中删除a之前的元素形成新序列A，在序列B中删除b之后的元素形成新序列B

（3）a > b，两个序列的中位数只能出现在[b，a)，在序列中A中删除a之后的元素形成新序列A，在序列B中删除b之前的元素形成新序列B

重复以上步骤。

三、算法代码

public static int searchMid(int [] a, int [] b){
		if(a.length != b.length){
			System.out.println("序列规模不一致，计算结果初始化为-1！");
			return -1;
		}
		int s1 = 0;
		int e1 = a.length - 1;
		int s2 = 0;
		int e2 = b.length - 1;
		int mid1,mid2;
		while(s1 < e1 && s2 < e2){
			mid1 = (s1 + e1) / 2;
			mid2 = (s2 + e2) / 2;
			if(a[mid1] == b[mid2]){
				return a[mid1];
			}
			if(a[mid1] < b[mid2]){
				s1 = mid1 + 1;
				e2 = mid2;
			}else{
				s2 = mid2 + 1;
				e1 = mid1;
			}
		}
		if(a[s1] < b[s2]){
			return a[s1];
		}else{
			return b[s2];
		}
	}

四、完整测试代码

public class package01 {

	public static void main(String [] args){
		int [] a = new int[]{1,2,3,4,5,11,13};
		int [] b = new int[]{6,7,8,9,10,12,14};
		int result = searchMid(a, b);
		System.out.print("两个递增序列的中位数为：" + result);
	}

	public static int searchMid(int [] a, int [] b){
		if(a.length != b.length){
			System.out.println("序列规模不一致，计算结果初始化为-1！");
			return -1;
		}
		int s1 = 0;
		int e1 = a.length - 1;
		int s2 = 0;
		int e2 = b.length - 1;
		int mid1,mid2;
		while(s1 < e1 && s2 < e2){
			mid1 = (s1 + e1) / 2;
			mid2 = (s2 + e2) / 2;
			if(a[mid1] == b[mid2]){
				return a[mid1];
			}
			if(a[mid1] < b[mid2]){
				s1 = mid1 + 1;
				e2 = mid2;
			}else{
				s2 = mid2 + 1;
				e1 = mid1;
			}
		}
		if(a[s1] < b[s2]){
			return a[s1];
		}else{
			return b[s2];
		}
	}
}

五、运行结果

两个递增序列的中位数为：8