LeetCode by JAVA - 4. Median of

package leetCode;

/**
 * Created by YaphetZhao on 2017/9/5.
 */
public class _4_MedianofTwoSortedArrays {
    /**
     * There are two sorted arrays nums1 and nums2 of size m and n respectively.
     * 有两个排序数组nums1和nums2分别大小为m和n。
     * <p>
     * Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
     * 找到两个排序数组的中值。整个运行时复杂度应该是O(log(m + n))。
     * 中值[median] （又称中位数）是指将统计总体当中的各个变量值按大小顺序排列起来，
     * 形成一个数列，处于变量数列中间位置的变量值就称为中位数，用Me表示。当变量值的项数N为奇数时，
     * 处于中间位置的变量值即为中位数；当N为偶数时，中位数则为处于中间位置的2个变量值的平均数.
     */
    public static void main(String args[]) {
        findMedianSortedArrays(new int[]{1, 2}, new int[]{1, 2});
    }

    public static 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;
    }

}