找出两个已经排好序的数组的中位数

问题：

给两个已经排好序的数组，一个长度为 m (m >= 1), 一个长度为 n (n >= 1)，找出这两个数组的中位数。时间复杂度要求为 O(m+n), 空间复杂度为 O(1)。

其实这个问题本身来讲是不难的，关键的关键，是对一些边界条件的处理。

思路：我们首先判断中位数的位置，如果 m+n 为奇数，那么中位数的位置是 第 (m+n+1)/2。 如果 m + n 为偶数，那么我们要找出第 (m+n)/2 和 第(m+n)/2 + 1, 然后求平均。

我们在两个数组上都分配一个“指针”指到起始位（假定A数组的指针为pa, B数组的指针为pb），然后根据它们值的大小，指针不断的向前推进，直到总的被遍历的数的个数为(m+n+1)/2 （奇数情况）或者为(m+n)/2 （偶数情况）。

我们在移动指针对数组中的数进行比较的时候，我们要考虑指针是否已经操过数组的大小，然后才能进行比较，这是一个非常值得注意的地方。

public float median(int[] A, int[] B) {
		
		int m = A.length;
		int n = B.length;
		
		int pa = 0;
		int pb = 0;
		
		// to check whether the median is one or two.
		boolean isEven = (m + n)%2 == 0 ? true : false;
		
		float median = 0;
		
		int i = 0;
		
		if (isEven == false) {
			while (true) {
				i++;
				if (pa >= A.length) {
					if (i == (m+n+1)/2) {
						median = B[pb]; 
						break;
					}
					pb++;				
				} else if (pb >= B.length) {
					if (i == (m+n+1)/2) {
						median = A[pa]; 
						break;
					}
					pa++;
				} else if (A[pa] <= B[pb]) {
					if (i == (m+n+1)/2) {
						median = A[pa]; 
						break;
					}
					pa++;
				} else {
					if (i == (m+n+1)/2) {
						median = B[pb]; 
						break;
					}
					pb++;
				}

			}
		} else {
			
			int median1 = 0;
			int median2 = 0;
			while (true) {
				i++; 
				if (pa >= A.length) {
					if (i == (m+n)/2) {
						median1 = B[pb];
						median2 = (pb < n-1 && B[pb+1] <= A[pa]) ? B[pb+1] : A[pa];
						median = (float) (median1 + median2)/2;
						break;
					}
					pb++;
				} else if (pb >= B.length) {
					if (i == (m+n)/2) {
						median1 = A[pa];
						median2 = (pa < m-1 && A[pa+1] <= B[pb]) ? A[pa+1] : B[pb];
						median = (float) (median1 + median2)/2;
						break;
					}
					pa++;
				} else if (A[pa] <= B[pb]) {
					if (i == (m+n)/2) {
						median1 = A[pa];
						median2 = (pa < m-1 && A[pa+1] <= B[pb]) ? A[pa+1] : B[pb];
						median = (float) (median1 + median2)/2;
						break;
					}
					pa++;
				} else {
					if (i == (m+n)/2) {
						median1 = B[pb];
						median2 = (pb < n-1 && B[pb+1] <= A[pa]) ? B[pb+1] : A[pa];
						median = (float) (median1 + median2)/2;
						break;
					}
					pb++;
				}
			}
		}

		return median;
	}