ค่ามัธยฐานของอาร์เรย์ที่จัดเรียงสองตัว

ค่ามัธยฐานคือตัวเลขตรงกลาง หรืออีกนัยหนึ่ง ค่ามัธยฐานคือการสังเกตตรงกลางในรายการที่เรียงลำดับ สอดคล้องกับเปอร์เซ็นต์สะสม 50%

ขนาดของอาร์เรย์ทั้งสองต้องเท่ากัน เราจะหาค่ามัธยฐานของอาร์เรย์สองอาร์เรย์ที่แยกจากกันในตอนแรก จากนั้นจึงเปรียบเทียบค่ามัธยฐานที่แยกจากกันเพื่อให้ได้ค่ามัธยฐานจริงของสองรายการ

อินพุตและเอาต์พุต

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.

อัลกอริทึม

ค่ามัธยฐาน(รายการ, n)

อินพุต: รายการข้อมูลและจำนวนข้อมูล

ผลลัพธ์: ค่ามัธยฐานของรายการที่กำหนด

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)

ป้อนข้อมูล - สองรายการที่เรียงและจำนวนรายการ

ผลลัพธ์ − ค่ามัธยฐานจากรายการที่จัดเรียงสองรายการ

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

ตัวอย่าง

#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";
}

ผลลัพธ์

Median is 6