牛客231765题解析：高效求解两个有序数组中位数的分治算法（附代码详解）
一、题目解读
牛客231765题要求求解两个有序数组的中位数。给定两个长度分别为m和n的有序数组arr1和arr2，需找到合并后数组的中位数。中位数定义为排序后位于中间位置的元素，若总长度为奇数则直接取中间值，偶数则取中间两个元素的平均值。本题的核心在于如何在O(log(m+n))时间内高效找到这个中位数，避免直接合并排序带来的O(m+n)复杂度。
二、解题思路
采用分治法，通过二分查找分割点来减少比较次数。关键思想是：在两个数组中找到合适的分割点（即arr1的第k1位置和arr2的第k2位置），使得分割后的左右两部分元素数量总和满足中位数的定义。通过比较分割点两侧的最大值（左部分）与最小值（右部分），判断当前分割是否满足条件，进而缩小搜索范围。通过二分法，将时间复杂度控制在O(log(m+n))。
三、解题步骤详解
1. 确定基准数组：确保arr1为较短数组，若arr2更短则交换，减少后续循环次数。
2. 二分查找分割点：在arr1中通过二分法寻找分割点partition1，根据总长度计算arr2的分割点partition2。
3. 处理边界情况：当partition1或partition2为0或数组末尾时，特殊处理边界值（如INT_MIN/INT_MAX），避免越界。
4. 判断分割有效性：比较两侧的最大值（左）与最小值（右），若满足maxLeft1 ≤ minRight2 且 maxLeft2 ≤ minRight1，则找到正确分割点。
5. 递归调整：若分割不满足条件，根据大小关系调整二分范围（缩小左侧或右侧），继续循环查找。
6. 返回结果：最终合并数组的上中位数为两个分割点左侧的最大值（即max(maxLeft1, maxLeft2)）。
四、代码与注释
class Solution {
public:
int getUpMedian(vector<int>& arr1, vector<int>& arr2) {
// 确保arr1是较短的数组
if (arr1.size() > arr2.size()) {
return getUpMedian(arr2, arr1); // 递归交换数组
}
int m = arr1.size();
int n = arr2.size();
int total = m + n;
int low = 0, high = m; // 二分范围初始化
while (low <= high) {
int partition1 = (low + high) / 2; // 当前分割点
int partition2 = (total + 1) / 2 - partition1; // 对应arr2的分割点
// 处理边界情况
int maxLeft1 = (partition1 == 0)? INT_MIN : arr1[partition1 - 1];
int minRight1 = (partition1 == m)? INT_MAX : arr1[partition1];
int maxLeft2 = (partition2 == 0)? INT_MIN : arr2[partition2 - 1];
int minRight2 = (partition2 == n)? INT_MAX : arr2[partition2];
// 找到正确的分割点
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
// 返回上中位数（合并数组中间位置的较大值）
return max(maxLeft1, maxLeft2);
}
else if (maxLeft1 > minRight2) {
// 分割点需要左移（缩小右侧范围）
high = partition1 - 1;
}
else {
// 分割点需要右移（扩大右侧范围）
low = partition1 + 1;
}
}
return -1; // 理论上不会执行到这里
}
};注释解析：通过递归交换数组长度确保arr1较短，利用二分法动态调整分割点，结合边界处理避免数组越界，最终通过比较分割点两侧的极值确定中位数位置。
五、总结
本解法巧妙利用分治与二分查找，将复杂的中位数问题转化为分割点的有效性验证。通过边界条件的严谨处理，避免了合并排序的高耗时，实现了O(log(m+n))时间复杂度。该算法适用于大规模有序数组场景，是解决中位数问题的经典优化方案。理解此算法有助于提升对分治思想和二分优化的应用能力。
原创内容 转载请注明出处
