按行排序矩阵中的中位数

Question

我试图理解使用以下代码在按行排序矩阵中查找中位数背后的逻辑：

int upperBound(vector<int>& matrix, int x, int C){
    int low = 0, high = C-1;
    int ans = C;
    
    while(low <= high){
        int mid = (low+high) / 2;
        if(matrix[mid] > x){
            ans = mid;
            high = mid -1;
        }
        else{
            low = mid +1;
        }
    }
    return ans;
}

int blackBox(vector<vector<int>>& matrix, int R, int C, int mid){
    int count = 0;
    for(int i = 0; i<R; i++){
        count += upperBound(matrix[i], mid, C);
    }
    return count;
}

int median(vector<vector<int>> &matrix, int R, int C){
    int low = INT_MAX;
    int high = INT_MIN;
    
    for(int  i =0; i<R; i++){
        low = min(low, matrix[i][0]);
        high = max(high, matrix[i][C-1]);
    }
    
    int req = (R*C) / 2;
    
    while(low <= high){
        int mid = (low+high) / 2;
        int smaller = blackBox(matrix, R, C, mid);
        if(smaller <= req) low = mid+1;
        else high = mid-1;
    }
    
    return low;
}

我的问题：

• 在median函数中，代表排序数组中间元素的mid变量是如何从矩阵转换而来的？
• 如果中间元素不存在于矩阵本身中并且只是矩阵/数组的最高值和最低值的平均值，会发生什么？在这种情况下，算法如何仍然找到正确的中位数？

任何解释或澄清将不胜感激！

Answer 1

1. “mid”变量如何来自表示排序数组中间元素的矩阵？

1. ‘mid’变量并不完全是排序后的中间元素 矩阵。相反，它代表当前的中间值 搜索范围在“低”和“高”之间。

2. 基于小于或等于“mid”的元素计数， 二分查找过程细化了这个范围。

3. 当该计数等于总数的一半时，即获得真正的中位数 元素数量。

2. 假设“mid”元素本身并不真正存在于矩阵中，并且它实际上是矩阵/数组的最高值和最低值的平均值。那么在这些情况下算法如何仍然找到正确的中位数？

1. 'mid'不一定是矩阵中的元素。我们正在做一个 对值范围而不是元素本身进行二分搜索。

2. 即使“mid”不在矩阵中，算法也能正确识别 中位数。关键在于那些小于的元素的计数 或等于“中”。通过这个计数细化“低”和“高”，算法 不断缩小范围，直到收敛到正确的中位数 值，必然在该范围内。

3. “low”的最后一个值（在 while 循环之后）将是最小值 使得矩阵中超过一半的元素小于或 等于它，因此使其成为中位数

.