LeetCode------尋找兩個有序數組的中位數

Java版一：

package tencent;

/**
 * 給定兩個大小為 m 和 n 的有序數組 nums1 和 nums2。
 * 
 * 請你找出這兩個有序數組的中位數，并且要求算法的時間複雜度為 O(log(m + n))。
 * 
 * 你可以假設 nums1 和 nums2 不會同時為空。
 * 
 * 示例 1:
 * 
 * nums1 = [1, 3] nums2 = [2]
 * 
 * 則中位數是 2.0 示例 2:
 * 
 * nums1 = [1, 2] nums2 = [3, 4]
 * 
 * 則中位數是 (2 + 3)/2 = 2.5
 * 
 * 來源：力扣（LeetCode）
 * 連結：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
 * 
 * @author BlueZ
 * 
 */
public class FindMedianSortedArrays {
//	執行用時 :3 ms, 在所有 Java 送出中擊敗了98.27%的使用者
//	記憶體消耗 :47.6 MB, 在所有 Java 送出中擊敗了9.69%的使用者
	public double findMedianSortedArrays(int[] A, int[] B) {
		int m = A.length;
		int n = B.length;
		if (m > n) { // to ensure m<=n
			int[] temp = A;
			A = B;
			B = temp;
			int tmp = m;
			m = n;
			n = tmp;
		}
		int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
		while (iMin <= iMax) {
			int i = (iMin + iMax) / 2;
			int j = halfLen - i;
			if (i < iMax && B[j - 1] > A[i]) {
				iMin = iMin + 1; // i is too small
			} else if (i > iMin && A[i - 1] > B[j]) {
				iMax = iMax - 1; // i is too big
			} else { // i is perfect
				int maxLeft = 0;
				if (i == 0) {
					maxLeft = B[j - 1];
				} else if (j == 0) {
					maxLeft = A[i - 1];
				} else {
					maxLeft = Math.max(A[i - 1], B[j - 1]);
				}
				if ((m + n) % 2 == 1) {
					return maxLeft;
				}

				int minRight = 0;
				if (i == m) {
					minRight = B[j];
				} else if (j == n) {
					minRight = A[i];
				} else {
					minRight = Math.min(B[j], A[i]);
				}

				return (maxLeft + minRight) / 2.0;
			}
		}
		return 0.0;
	}

	public static void main(String[] args) {
		int[] A = { 1, 3 };
		int[] B = { 6, 8 };
		System.out.println(new FindMedianSortedArrays().findMedianSortedArrays(
				A, B));
	}
}