牛客231765题详解：二分查找法高效求解两个有序数组的下中位数

12小时前牛客题解36

一、问题背景

在算法面试中，求解两个有序数组的下中位数是一个经典问题。上中位数指的是将两个数组合并排序后，位于中间位置的较小值。本文介绍的解法时间复杂度为O(log(min(m,n)))，空间复杂度O(1)，是效率极高的解决方案。

二、核心算法思路

该算法基于二分查找思想，通过巧妙的分割策略在两个数组中找到合适的分割点，使得：

左半部分元素数量等于右半部分
左半部分最大值小于等于右半部分最小值

三、代码实现详解

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 low = 0, high = m;  // 只在较短的数组上二分
        int total = m + n;
        
        while (low <= high) {
            // 计算分割点
            int partition1 = (low + high) / 2;  // arr1的分割点
            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; // 理论上不会执行到这里（因为输入是有序数组）
    }
};