004-寻找两个有序数组的中位数

Description

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数。
要求算法的时间复杂度为 O(log(m + n))
你可以假设 nums1 和 nums2 不会同时为空。

Example
Input:nums1 = [1, 3]
      nums2 = [2]
Output: 2.0

Input: nums1 = [1, 2]
       nums2 = [3, 4]
Output:  (2 + 3)/2 = 2.5


Input: nums1 = [1,2,3,7,8,9,10]
       nums2 = [-2,-1,4,5,7,9]
Output:  5
Solution

分割两个数组,分为leftA,rightA, leftB,rightB, leftA+leftB的长度等于rightA+rightB 左边数组的最大值等于右边数组的最小值时,就找到了中间值

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    m := len(nums1)
    n := len(nums2)
    if m == 0 {
        return medianof(nums2)
    }
    if n == 0 {
        return medianof(nums1)
    }
    if m > n { //确保nums1数组长度比nums2边短
        findMedianSortedArrays(nums2,nums1)
    }
    halflen := (m + n +1)/2
    iMin := 0 //nums1的起始分割点 iMin < m的总长
    iMax := m

    //使用二分法查找分割点
    for iMin <= iMax {
        i := (iMin + iMax)/2
        j := halflen - i
        if i < iMax && nums2[j - 1] > nums1[i] {
            //取值位置偏小,需要右移最小位置
            iMin =  i + 1
        }else if i > iMin &&  nums1[i -1] > nums2[j] {
            iMax = i -1   //i的位置太大
        }else {
            maxLeft := 0
            if i == 0 {
                maxLeft = nums2[j - 1]
            }else if j == 0 {
                maxLeft = nums1[i -1]
            }else {
                maxLeft = maxInt(nums1[i-1],nums2[j-1])
            }
            if (m + n)%2 ==1 {
                return float64(maxLeft)
            }

            minRight := 0
            if i == m {
                minRight = nums2[j]
            }else if j == n {
                minRight = nums1[i]
            }else {
                minRight = minInt(nums1[i],nums2[j])
            }
            return float64(maxLeft +minRight)/2.0
        }
    }
    return 0.0
}

func medianof(nums []int)float64  {
    l := len(nums)
    if l == 0 {
        return 0
    }
    if l%2 == 0 {
        return float64(nums[l/2-1]+nums[l/2])/2.0
    }
    return float64(nums[l/2])
}

func minInt(a,b int)int  {
    if a > b {
        return b
    }
    return a
}

func maxInt(a,b int)int  {
    if a > b {
        return a
    }
    return b
}

leetCode地址
Median of Two Sorted Arrays