题解 | #牛的体重排序#

题目考察的知识点: 二分查找

题目解答方法的文字分析:

由于两个序列都是有序的，找中位数就是找到中间的第k个数。
分别找到两个数组中的第k/2数字，较小的这部分可以说明答案不在里面，将这部分排出查找范围，一步步缩小范围直到找到答案

本题解析所用的编程语言:Java

完整且正确的编程代码

import java.util.*;


public class Solution {
    public double findMedianSortedArrays (int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m == 0) return n % 2 == 0 ? (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0 : nums2[n / 2];
        if (n == 0) return m % 2 == 0 ? (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0 : nums1[m / 2];
        int total = m + n;
        if (total % 2 == 0) return (findKth(nums1, 0, nums2, 0,total / 2) + 
                                    findKth(nums1, 0, nums2, 0, total / 2 + 1)) / 2.0;
        else return findKth(nums1, 0, nums2, 0, total / 2 + 1);
    }

    private double findKth(int[] a, int a_begin, int[] b, int b_begin, int k) {
        if (a_begin >= a.length) return b[b_begin + k - 1];
        if (b_begin >= b.length) return a[a_begin + k - 1];
        if (k == 1) return Math.min(a[a_begin], b[b_begin]);
        int mid_a = Integer.MAX_VALUE;
        int mid_b = Integer.MAX_VALUE;
        if (a_begin + k / 2 - 1 < a.length) mid_a = a[a_begin + k / 2 - 1];
        if (b_begin + k / 2 - 1 < b.length) mid_b = b[b_begin + k / 2 - 1];
        if (mid_a < mid_b) {
            return findKth(a, a_begin + k / 2, b, b_begin, k - k / 2);
        } else return findKth(a, a_begin, b, b_begin + k / 2, k - k / 2);
    }
}