C++程序在按行排序的矩阵中找到中位数

给定大小为r * c的按行排序的矩阵，需要在矩阵中找到中位数。假设r * c始终是奇数。

例子：

输入: 1 3 5
2 6 9
3 6 9
输出: 中位数是5
如果我们将所有值放入已排序数组A[]中= 1 2 3 3 5 6 6 9 9)

输入：1 3 4
2 5 6
7 8 9
输出：中位数是5

简单方法 ：解决此问题的最简单方法是将给定矩阵的所有元素存储在大小为r * c的数组中。然后，我们可以对数组进行排序并在O(r * clog（r * c）)中查找中位数元素，或者我们可以使用此处讨论的方法在O（r * c）中查找中位数。两种情况下都需要O(r * c)的辅助空间。

一个 高效的方法 解决此问题是使用二进制搜索算法。它的想法是：对于数字来说，中位数应恰好有(n / 2)个数字小于这个数字。因此，我们尝试找到小于所有数字的数量。以下是此方法的逐步算法：

算法：

首先，我们找到矩阵中的最小和最大元素。可以通过将每行的第一个元素进行比较来轻松找到最小元素，类似地，可以通过将每行的最后一个元素进行比较来找到最大元素。
然后，在我们的范围内从最小到最大使用二进制搜索，我们找到最小值和最大值的中间值，并获取小于我们的中间值的数字的数量。然后相应地更改最小值或最大值。
对于中位数来说，应该有(r * c) / 2个数字比该数字小。因此，对于每个数字，我们都要通过在矩阵的每行中使用upper_bound()获取该数字的少于所需数量的数字的计数，如果小于所需数量，则中位数必须大于所选数字，否则中位数必须小于或等于所选数字。

以下是上述方法的实现：

// C++ program to find median of a matrix
// sorted row wise
#include<bits/stdc++.h>
using namespace std;

const int MAX = 100;

// function to find median in the matrix
int binaryMedian(int m[][MAX], int r ,int c)
{
    int min = INT_MAX, max = INT_MIN;
    for (int i=0; i<r; i++)
    {
        // Finding the minimum element
        if (m[i][0] < min)
            min = m[i][0];

        // Finding the maximum element
        if (m[i][c-1] > max)
            max = m[i][c-1];
    }

    int desired = (r * c + 1) / 2;
    while (min < max)
    {
        int mid = min + (max - min) / 2;
        int place = 0;

        // Find count of elements smaller than mid
        for (int i = 0; i < r; ++i)
            place += upper_bound(m[i], m[i]+c, mid) - m[i];
        if (place < desired)
            min = mid + 1;
        else
            max = mid;
    }
    return min;
}

// driver program to check above functions
int main()
{
    int r = 3, c = 3;
    int m[][MAX]= { {1,3,5}, {2,6,9}, {3,6,9} };
    cout << "Median is " << binaryMedian(m, r, c) << endl;
    return 0;
}