# 在按行排序的矩陣中找到中位數 > 原文： [https://www.geeksforgeeks.org/find-median-row-wise-sorted-matrix/](https://www.geeksforgeeks.org/find-median-row-wise-sorted-matrix/) 給定大小為 r * c 的按行排序的矩陣，我們需要找到給定矩陣的中位數。 假定 r * c 總是奇數。 例子： ``` Input : 1 3 5 2 6 9 3 6 9 Output : Median is 5 If we put all the values in a sorted array A[] = 1 2 3 3 5 6 6 9 9) Input: 1 3 4 2 5 6 7 8 9 Output: Median is 5 ``` **簡單方法**：解決此問題的最簡單方法是將給定矩陣的所有元素存儲在大小為 r * c 的數組中。 然后，我們可以對數組進行排序并在 O（r * clog（r * c））中找到中值元素，也可以使用此處討論的[方法](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/)在 O（r * c）中找到中值。 在兩種情況下，所需的輔助空間均為 O（r * c）。 解決此問題的有效方法**是使用[二分搜索](https://www.geeksforgeeks.org/binary-search/)算法。 這個想法是，要使一個數成為中位數，應有準確的（n / 2）個數小于該數。 因此，我們嘗試找到少于所有數字的數字計數。 以下是此方法的分步算法： **算法****： 1. 首先，我們在矩陣中找到最小和最大元素。 可以通過比較每行的第一個元素輕松找到最小元素，類似地，可以通過比較每行的最后一個元素找到最大元素。 2. 然后，我們對從最小值到最大值的數字范圍進行二分搜索，找到最小值和最大值的中位數，并得到小于中位數的數量計數。 并相應地更改最小值或最大值。 3. 為了使數字中位數，應該有比該數字小（r * c）/ 2 個數字。 因此，對于每個數字，我們通過在矩陣的每一行中使用 upper_bound（）來獲得小于該數字的計數，如果小于所需計數，則中位數必須大于所選數字，否則中位數必須小于 等于或等于所選數字。 下面是上述方法的實現： ## C++ ```cpp // 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; } ``` ## Java ```java // Java program to find median of a matrix // sorted row wise import java.util.Arrays; public class MedianInRowSorted? { ????// function to find median in the matrix ????static int binaryMedian(int m[][],int r, int c) ????{ ????????int max = Integer.MIN_VALUE; ????????int min = Integer.MAX_VALUE; ????????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; ????????????int get = 0; ????????????// Find count of elements smaller than mid ????????????for(int i = 0; i < r; ++i) ????????????{ ????????????????get = Arrays.binarySearch(m[i],mid); ????????????????// If element is not found in the array the? ????????????????// binarySearch() method returns? ????????????????// (-(insertion_point) - 1). So once we know? ????????????????// the insertion point we can find elements ????????????????// Smaller than the searched element by the? ????????????????// following calculation ????????????????if(get < 0) ????????????????????get = Math.abs(get) - 1; ????????????????// If element is found in the array it returns? ????????????????// the index(any index in case of duplicate). So we go to last ????????????????// index of element which will give? the number of? ????????????????// elements smaller than the number including? ????????????????// the searched element. ????????????????else ????????????????{ ????????????????????while(get < m[i].length && m[i][get] == mid) ????????????????????????get += 1; ????????????????} ????????????????place = place + get; ????????????} ????????????if (place < desired) ????????????????min = mid + 1; ????????????else ????????????????max = mid; ????????} ????????return min; ????} ????// Driver Program to test above method. ????public static void main(String[] args)? ????{ ????????int r = 3, c = 3; ????????int m[][]= { {1,3,5}, {2,6,9}, {3,6,9} }; ????????System.out.println("Median is " + binaryMedian(m, r, c)); ????} } // This code is contributed by Sumit Ghosh ``` ## Python3 ```py # Python program to find median of matrix # sorted row wise from bisect import bisect_right as upper_bound MAX = 100; # Function to find median in the matrix def binaryMedian(m, r, d): ????mi = m[0][0] ????mx = 0 ????for i in range(r): ????????if m[i][0] < mi: ????????????mi = m[i][0] ????????if m[i][d-1] > mx : ????????????mx =? m[i][d-1] ????desired = (r * d + 1) // 2 ????while (mi < mx): ????????mid = mi + (mx - mi) // 2 ????????place = [0]; ????????# Find count of elements smaller than mid ????????for i in range(r): ?????????????j = upper_bound(m[i], mid) ?????????????place[0] = place[0] + j ????????if place[0] < desired: ????????????mi = mid + 1 ????????else: ????????????mx = mid ????print ("Median is", mi) ????return???? # Driver code r, d = 3, 3 m = [ [1, 3, 5], [2, 6, 9], [3, 6, 9]] binaryMedian(m, r, d) # This code is contributed by Sachin BIsht ``` Output: ``` Median is 5 ``` **時間復雜度**：O（32 * r * log（c））。 上限函數將花費 log（c）時間，并針對每一行執行。 并且由于數字的最大值為 32 位，因此從最小值到最大值的二分搜索將最多執行 32（log2（2 ^ 32）= 32）個操作。 **輔助空間**：`O(1)`