LeetCode No4 寻找两个正序数组的中位数

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        boolean flag = (n+m)%2==0;
        int mid = (n+m)/2+1;
        int i = 0, j = 0;
        int a = 0, b = 0;
        int cnt = 1;
        while( i<n || j < m ) {
            a = b;
            if( i!=n ) {
                if( j!=m ) {
                    if( nums1[i] < nums2[j] ) {
                        b = nums1[i];
                        i ++;
                    } else {
                        b = nums2[j];
                        j ++;
                    }
                } else {
                    b = nums1[i];
                    i ++;
                }
            } else {
                b = nums2[j];
                j ++;
            }
            if( cnt == mid ) {
                break;
            }
            cnt ++;
        }
        if( flag ) {
            return (a+b)/2.0;
        }
        return b;
    }
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        if( n > m ) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int left = 0;
        int rigth = n;
        int i = 0;
        int j = 0;

        // 定义的分割线需要满足 nums1[i-1]<=nums2[j] && nums1[j-1]<=nums2[i]
        // 1 3 5 | 8(i) 9
        // 2 4 6 | 7(j) 10 12
        // 左边数字个数应该为 (n+m+1)/2 = i + j
        while( left<rigth ) {
            i = (left + rigth +1 ) / 2;
            j = (n+m+1)/2-i;
            // 二分确定能满足条件的分割线
            if( nums1[i-1]>nums2[j] ) {
                rigth = i - 1;
            } else {
                left = i;
            }
        }
        i = left;
        j = (n+m+1)/2-i;
        // 边界处理
        int numsI1 = i==0? Integer.MIN_VALUE: nums1[i-1];
        int numsI = i==n? Integer.MAX_VALUE: nums1[i];
        int numsJ1 = j==0? Integer.MIN_VALUE: nums2[j-1];
        int numsJ = j==m? Integer.MAX_VALUE: nums2[j];
        if( (n+m)%2 == 1 ) {
            return Math.max(numsI1, numsJ1);
        } else {
            return (Math.max(numsI1, numsJ1) + Math.min(numsI, numsJ)) * 0.5;
        }
    }
}