算法 || 分治法【寻找两个等长有序序列的中位数】java

分治法是一种常用的算法设计策略，特别适用于解决可以分解成若干相同子问题的问题。对于寻找两个等长有序序列的中位数，我们可以利用这个策略来设计一个高效的解决方案。这里是一个简单的Java实现思路：

首先，我们将原问题分解为两个子问题：
1. 找到第一个序列的中位数
2. 对于第二个序列，如果长度小于等于第一个序列，找到它的中位数；如果长度大于第一个序列，找到它的一半位置对应的值。

然后递归地求解这两个子问题，直到子问题规模足够小可以直接计算出结果。当两个子序列的总长度为奇数时，中位数就是第一个序列的中位数；当总长度为偶数时，中位数则是两部分中位数的平均值。

以下是简化的Java代码示例：

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int len = nums1.length + nums2.length;
    if (len % 2 == 0) { // 总长度偶数
        int mid = len / 2;
        return (findKth(nums1, nums2, mid) + findKth(nums1, nums2, mid - 1)) / 2.0;
    } else { // 总长度奇数
        return findKth(nums1, nums2, len / 2);
    }
}

private int findKth(int[] nums1, int[] nums2, int k) {
    int l = 0, r = nums1.length;
    while (l < r) {
        int m1 = l + (r - l) / 2;
        int m2 = k - m1; // 对应位置在nums2中的索引
        if (m2 < nums2.length && (m1 == 0 || nums1[m1 - 1] > nums2[m2])) {
            r = m1;
        } else {
            l = m1 + 1;
        }
    }
    return l <= nums1.length ? nums1[l - 1] : nums2[l - 2];
}