Trung vị là các số ở giữa, nói cách khác, giá trị trung vị là quan sát ở giữa trong một danh sách có thứ tự. Nó tương ứng với tỷ lệ phần trăm tích lũy là 50%.
Kích thước của hai mảng phải bằng nhau, lúc đầu chúng tôi sẽ tìm trung vị của hai mảng riêng biệt, sau đó so sánh các trung vị riêng biệt để có được trung vị thực tế của hai danh sách.
Đầu vào và Đầu ra
Input: Two sorted array are given. Array 1: {1, 2, 3, 6, 7} Array 2: {4, 6, 8, 10, 11} Output: The median from two array. Here the median value is 6. Merge the given lists into one. {1, 2, 3, 4, 6, 6, 7, 8, 10, 11} From the merged list find the average of two middle elements. here (6+6)/2 = 6.
Thuật toán
trung vị (danh sách, n)
Đầu vào: Danh sách dữ liệu và số lượng dữ liệu.
Đầu ra: Giá trị trung bình của danh sách đã cho.
Begin if the list has even number of data, then return (list[n/2] + list[n/2-1])/2 else return list[n/2] End
findMedian (list1, list2, n)
Đầu vào - Hai danh sách được sắp xếp và số lượng danh sách.
Đầu ra - Giá trị trung bình từ hai danh sách đã sắp xếp.
Begin if n <= 0, then it is invalid, and return invalid number if n = 1, then return (list1[0] + list2[0])/2 if n = 2, then return ((max of list1[0], list2[0]) + (min of list1[1], list2[1]))/2 med1 := median(list1, n) med2 := median(list2, n) if med1 = med2, then return med1 if med1 < med2, then if item has even number of data, then subList := data from list2, from 0 to n/2 – 1 data return findMedian(subList, list1, n – (n/2) + 1) subList := data from list2, from 0 to n/2 data return findMedian(subList, list2, n – (n/2)) End
Ví dụ
#include<iostream> using namespace std; int median(int list[], int n) { if (n%2 == 0) //when array containts even number of data return (list[n/2] + list[n/2-1])/2; else //for odd number of data return list[n/2]; } intfindMedian(int list1[], int list2[], int n) { if (n <= 0) return -1; //invalid length of lists if (n == 1) return (list1[0] + list2[0])/2; //for single element simply get average from two array if (n == 2) return (max(list1[0], list2[0]) + min(list1[1], list2[1])) / 2; int med1 = median(list1, n); //Find median from first array int med2 = median(list2, n); //Find median from second array if (med1 == med2) //when both medians are same, they are the final median return med1; if (med1 < med2) { if (n % 2 == 0) return findMedian(list1 + n/2 - 1, list2, n - n/2 +1); return findMedian(list1 + n/2, list2, n - n/2); } if (n % 2 == 0) //when med1 > med2 return findMedian(list2 + n/2 - 1, list1, n - n/2 + 1); return findMedian(list2 + n/2, list1, n - n/2); } int main() { int list1[] = {1, 2, 3, 6, 7}; int list2[] = {4, 6, 8, 10, 11}; int n1 = 5; int n2 = 5; if (n1 == n2) cout<< "Median is "<<findMedian(list1, list2, n1); else cout<< "Doesn't work for lists of unequal size"; }
Đầu ra
Median is 6