การหาค่ามัธยฐานของอาร์เรย์ที่เรียงลำดับสองชุด

ค่ามัธยฐาน (Median) คือค่ากลางของชุดข้อมูลที่เรียงลำดับแล้ว ซึ่งสอดคล้องกับเปอร์เซ็นไทล์ที่ 50 ในการหาค่ามัธยฐานของอาร์เรย์สองชุดที่มีขนาดเท่ากัน เราจะหาค่ามัธยฐานของแต่ละอาร์เรย์ก่อน แล้วจึงเปรียบเทียบค่ามัธยฐานทั้งสองเพื่อหาค่ามัธยฐานรวมของข้อมูลทั้งหมด

การรับค่าและแสดงผล

Input: อาร์เรย์ที่เรียงลำดับสองชุด
Array 1: {1, 2, 3, 6, 7}
Array 2: {4, 6, 8, 10, 11}

Output: ค่ามัธยฐานจากสองอาร์เรย์
รวมอาร์เรย์ทั้งสอง: {1, 2, 3, 4, 6, 6, 7, 8, 10, 11}
หาค่าเฉลี่ยของสองค่ากลาง: (6 + 6) / 2 = 6

อัลกอริทึม

median(list, n)

Input: รายการข้อมูล และจำนวนข้อมูล

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

Begin
  if จำนวนข้อมูลเป็นเลขคู่ then
    return (list[n/2] + list[n/2 - 1]) / 2
  else
    return list[n/2]
End

findMedian(list1, list2, n)

Input: สองรายการที่เรียงลำดับแล้ว และจำนวนข้อมูล

Output: ค่ามัธยฐานจากสองรายการที่เรียงลำดับ

Begin
  if n <= 0 then
    return ค่าที่ไม่ถูกต้อง
  if n = 1 then
    return (list1[0] + list2[0]) / 2
  if n = 2 then
    return (max(list1[0], list2[0]) + min(list1[1], list2[1])) / 2
  
  med1 := median(list1, n)
  med2 := median(list2, n)
  
  if med1 = med2 then
    return med1
  
  if med1 < med2 then
    if จำนวนข้อมูลเป็นเลขคู่ then
      subList := ข้อมูลจาก list2 ตั้งแต่ 0 ถึง n/2 - 1
      return findMedian(subList, list1, n - (n/2) + 1)
    else
      subList := ข้อมูลจาก list2 ตั้งแต่ 0 ถึง n/2
      return findMedian(subList, list2, n - (n/2))
End

ตัวอย่างโค้ด (C++)

#include <iostream>
using namespace std;

int median(int list[], int n) {
  if (n % 2 == 0)
    return (list[n/2] + list[n/2 - 1]) / 2;
  else
    return list[n/2];
}

int findMedian(int list1[], int list2[], int n) {
  if (n <= 0) return -1;
  if (n == 1) return (list1[0] + list2[0]) / 2;
  if (n == 2) return (max(list1[0], list2[0]) + min(list1[1], list2[1])) / 2;
  
  int med1 = median(list1, n);
  int med2 = median(list2, n);
  
  if (med1 == med2) 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)
    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, 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