题解 | #牛的体重排序#

知识点：二分查找

题目要求时间复杂度O(log(m + n))，故我们不能通过遍历两个数组来找中位数，而是对两个数组进行二分查找，我们先找出较短数组的中间值，然后去判断该中间值是否符合条件。

对于两个数组来说，总个数是m+n，总数若为偶数，中位数是第(m+n) / 2个元素和第(m+n) / 2 + 1个元素的平均值，若为奇数，中位数是第(m+n) / 2 + 1个元素。我们可以先根据较短数组找到中间值mid，然后再定位到较长数组的中间值，此时开始判断两个中间值的四个中间元素，是否符合左边值都小于右边值，若符合，则说明找到了中位数，否则，则需要调整中间位置，继续以上判断。

Java题解如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weightsA int整型一维数组 
     * @param weightsB int整型一维数组 
     * @return double浮点型
     */
    public double findMedianSortedArrays (int[] weightsA, int[] weightsB) {
        // write code here
        int m = weightsA.length, n = weightsB.length;
        if(m > n) {
            return findMedianSortedArrays(weightsB, weightsA);
        }
        int left = 0, right = m;
        while(left <= right) {
            int midA = left + ((right - left) >> 1);
            int midB = (m + n + 1) / 2 - midA;
            int maxLeftA = midA - 1 >= 0? weightsA[midA - 1]: Integer.MIN_VALUE;
            int minRightA = midA < m? weightsA[midA]: Integer.MAX_VALUE;
            int maxLeftB = midB - 1 >= 0? weightsB[midB - 1]: Integer.MIN_VALUE;
            int minRightB = midB < n? weightsB[midB]: Integer.MAX_VALUE;
            if(maxLeftA <= minRightB && maxLeftB <= minRightA) {
                if((m + n) % 2 == 0) {
                    int maxLeft = Math.max(maxLeftA, maxLeftB);
                    int minRight = Math.min(minRightA, minRightB);
                    return (maxLeft + minRight) / 2.0;
                }else {
                    return Math.max(maxLeftA, maxLeftB);
                }
            }else if(maxLeftA > minRightB) {
                right = midA - 1;
            }else {
                left = midA + 1;
            }
        }
        return -1.0;
    }
}