মেডিয়ান হলো একটি সাজানো তালিকার মধ্যবর্তী সংখ্যা। অর্থাৎ, একটি ক্রমবদ্ধ তালিকায় মধ্যবর্তী পর্যবেক্ষণই মেডিয়ান মান। এটি ৫০% কিউমুলেটিভ শতাংশের সাথে মিলে যায়।
ইনপুট এবং আউটপুট
ইনপুট: দুটি সর্ট করা অ্যারে দেওয়া আছে।
অ্যারে ১: {1, 2, 3, 6, 7}
অ্যারে ২: {4, 6, 8, 10, 11}
আউটপুট: দুটি অ্যারে থেকে মেডিয়ান। এখানে মেডিয়ান মান ৬।
দুটি তালিকাকে একত্রিত করলে: {1, 2, 3, 4, 6, 6, 7, 8, 10, 11}
একত্রিত তালিকায় দুটি মধ্যবর্তী উপাদানের গড়: (6+6)/2 = 6।
এলগরিদম
median(list, n)
ইনপুট: ডেটার তালিকা এবং ডেটার সংখ্যা।
আউটপুট: প্রদত্ত তালিকার মেডিয়ান।
শুরু
যদি তালিকায় জোড় সংখ্যক ডেটা থাকে, তবে
return (list[n/2] + list[n/2-1])/2
অন্যথায়
return list[n/2]
শেষ
findMedian(list1, list2, n)
ইনপুট: দুটি সর্ট করা তালিকা এবং তালিকার আকার।
আউটপুট: দুটি সর্ট করা তালিকা থেকে মেডিয়ান।
শুরু
যদি n <= 0, তবে
এটি অবৈধ, অবৈধ সংখ্যা ফেরত দিন
যদি n = 1, তবে
return (list1[0] + list2[0])/2
যদি n = 2, তবে
return ((max(list1[0], list2[0]) + min(list1[1], list2[1]))/2
med1 := median(list1, n)
med2 := median(list2, n)
যদি med1 = med2, তবে
return med1
যদি med1 < med2, তবে
যদি উপাদান জোড় সংখ্যক থাকে, তবে
subList := list2 থেকে 0 থেকে n/2 - 1 ডেটা
return findMedian(subList, list1, n - (n/2) + 1)
subList := list2 থেকে 0 থেকে n/2 ডেটা
return findMedian(subList, list2, n - (n/2))
শেষ
উদাহরণ (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) // যখন 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
