No.4.go

func partition(nums1 []int, nums2 []int) (int, int) {
    n1 := len(nums1)
    n2 := len(nums2)
    half := (n1+n2) >> 1

    // n1 ≤ n2 => n1 ≤ half=(n1+n2)>>1 ≤ n2
    // i want to have left part ≤ right part

    // now, I split nums1 and nums2 in a way such as:
    // [0;m1)+[m1;n1+1) and [0;m2)+[m2;n2+1)
    // and m1+m2 == half
    // this means, (n1-m1)+(n2-m2) ≥ m1+m2

    l, r := -1, n1+1
    for l < r-1 {
        // m1 is in range [0;n1]
        m1 := int(uint(l+r)/2)
        // m1≤n1≤half => 0≤m2
        m2 := half-m1
        // max(m2)=half-min(m1)=half ≤ n2 (equality is possible)
        // thus: m2 is in range [0;n2]

        // m1-1 | m1
        // check that left part is more than the right part

        l1_leq_r2 := false
        if m2 == n2 || m1 == 0 {
            // L1 ≤ R2
            l1_leq_r2 = true
        } else {
            // m2 < n2 AND m1 > 0
            l1_leq_r2 = nums1[m1-1] <= nums2[m2]
        }

        l2_leq_r1 := false
        if m1 == n1 || m2 == 0 {
            l2_leq_r1 = true
        } else {
            l2_leq_r1 = nums2[m2-1] <= nums1[m1]
        }

        // there can be the only 1 point, where
        // left parts ≤ right parts
        if l1_leq_r2 && l2_leq_r1 {
            return m1, m2
        }

        // otherwise, we should continue our search
        if l1_leq_r2 {
            // !l2_leq_r1
            // this means, that nums2[m2-1] > nums1[m1]
            // we should move some right part of nums1 into left
            l = m1
        } else {
            r = m1
        }
    }

    // on output we will have (l,l+1)
    m1 := int(uint(l+r)/2)
    return m1, half-m1
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    n1 := len(nums1)
    n2 := len(nums2)
    n := n1+n2
    if n1 > n2 {
        n1, n2 = n2, n1
        nums1, nums2 = nums2, nums1
    }

    // n1 <= n2:
    /*
        Core idea is to find {m1,m2} such as
        LeftSize = len(nums1[0:m1])+len(nums2[0:m2])
        RightSize = len(nums1[m1:]) + len(nums2[m2:])
        LeftSize ≤ RightSize ≤ LeftSize+1
        so we split both arrays in a way to have left part and right part almost equal (for odd n1+n2)
        and exactly equal for even n1+n2

        and moreover all of the items in LeftPart ≤ all of the items in RightPart
        Note: RightPart can be bigger on 1 item
    */
    m1, m2 := partition(nums1, nums2)
    // m1 is in [0;n1]
    // m2 is in [0;n2]
    if n % 2 == 1 {
        // odd, solution is in right part:
        // just take minimal of 2 of them
        // min(nums2[m2], nums1[m1])
        if m1 == n1 {
            return float64(nums2[m2])
        } else if m2 == n2 {
            return float64(nums1[m1])
        } else if nums1[m1] <= nums2[m2] {
            return float64(nums1[m1])
        } else {
            return float64(nums2[m2])
        }
    } else {
        // even, solution is avg of left_max and right_min
        var left_max int
        if m1 == 0 {
            left_max = nums2[m2-1]
        } else if m2 == 0 {
            left_max = nums1[m1-1]
        } else if nums2[m2-1] <= nums1[m1-1] {
            left_max = nums1[m1-1]
        } else {
            left_max = nums2[m2-1]
        }

        var right_min int
        if m1 == n1 {
            right_min = nums2[m2]
        } else if m2 == n2 {
            right_min = nums1[m1]
        } else if nums1[m1] <= nums2[m2] {
            right_min = nums1[m1]
        } else {
            right_min = nums2[m2]
        }

        return float64(right_min+left_max)/2
    }
}