Go题解 | #在两个长度相等的排序数组中找到上中位数#

package main

/**
 * find median in two sorted array
 * @param arr1 int整型一维数组 the array1
 * @param arr2 int整型一维数组 the array2
 * @return int整型
*/
func findMedianinTwoSortedAray( arr1 []int ,  arr2 []int ) int {
    // write code here
    len := len(arr1)
    if arr1[len - 1] <= arr2[0] {
        return arr1[len - 1]
    }
    if arr2[len - 1] <= arr1[0] {
        return arr2[len - 1]
    }

    lo, hi := 0, len - 1
    k := len - 1
    for lo < hi {
        mid := (lo + hi + 1) / 2
        x := k - mid
        if arr1[mid] == arr2[x] {
            return arr1[mid]
        } else if arr1[mid] > arr2[x] {
            hi = mid - 1
        } else {
            lo = mid
        }
    }
    if arr1[lo] > arr2[k - 1 - lo] {
        return arr1[lo]
    } else {
        return arr2[k - 1 - lo]
    }
}

由于两个数组长度相等，上中位数应该是从0开始数第len - 1个数。

先排除数组1最大值小于等于数组2最小值的简单情况，以及相反的另一种简单情况。

然后在数组1内部进行二分，mid = (lo + hi + 1) / 2 . 因为要找的是第len个数，因此数组二内部的指针就设置为 x = len - 1 - mid。

每个循环来看，数组1内小于等于arr1[mid]的数有mid + 1个，数组2内小于等于arr2[x]的数有x + 1个。由于mid + 1 + x + 1 = len + 1，那么arr1[mid]和arr2[x]中更大的那个数，一定不可能是我们要找的，因为我们要找的是第len个数，所以如果arr1[mid]>arr2[x]，就让hi=mid - 1。如果arr1[mid]==arr2[x]就直接输出。否则继续考察，由于不能排除arr1[mid]恰好是上中位数，让lo=mid。

不管怎样，循环退出后，根据上面的分析arr1[lo] 可能是要找的，也可能不是，但arr1[lo + 1]肯定不是。那么取arr1[lo]和arr2[len - 2 - lo]更大的那个输出。