เราจะพัฒนาโปรแกรม C++ เพื่อหาค่ามัธยฐาน (median) ของอาร์เรย์ที่จัดเรียงแล้วสองอาร์เรย์ โดยใช้วิธีการค้นหาแบบทวิภาค (Binary Search approach)
อัลกอริทึม
Begin ฟังก์ชัน median() กับอาร์เรย์ทั้งสองและดัชนีเริ่มต้นและสิ้นสุดของแต่ละอาร์เรย์ ซึ่งมีสองอาร์เรย์และองค์ประกอบของพวกเขาเป็นอาร์กิวเมนต์ A) คำนวณความยาวอาร์เรย์เป็น e1 - s1 โดยที่ e1 และ s1 เป็นดัชนีสิ้นสุดและเริ่มต้น B) ถ้าความยาวเป็น 2 หรือ 1 ให้คำนวณค่ามัธยฐานของอาร์เรย์ตามความยาวคู่หรือคี่ พิมพ์ผลลัพธ์ C) ตรวจสอบว่าค่ามัธยฐานแต่ละอันเท่ากันหรือไม่ ถ้าใช่ ให้พิมพ์ผลลัพธ์ D) ถ้าเงื่อนไขข้างต้นสองอย่างเป็นจริง ตรวจสอบว่า m > m2 แล้วค่ามัธยฐานรวมจะอยู่ในครึ่งแรกของอาร์เรย์แรก หรือครึ่งหลังของอาร์เรย์ที่สอง E) ถ้า m1 < m2 ค่ามัธยฐานรวมจะอยู่ในครึ่งหลังของอาร์เรย์แรก หรือครึ่งแรกของอาร์เรย์ที่สอง F) เรียก median() แบบรีคอร์ซีฟ (recursively) พร้อมดัชนีเริ่มต้นและสิ้นสุดที่อัปเดตแล้ว End
ตัวอย่างโค้ด
#include<iostream> using namespace std; void median(float a1[], int s1, int e1, float a2[], int s2, int e2) { float m1, m2; if((e1-s1+1)%2 == 0) { if(e1-s1 == 1) { m1 = ((a1[s1]<a2[s2]?a1[s1]:a2[s2])+(a1[e1]>a2[e2]?a1[e1]:a2[e2]))/2; cout<<m1; return; } m1 = (a1[(e1+s1)/2]+a1[(e1+s1)/2+1])/2; m2 = (a2[(e2+s2)/2]+a2[(e2+s2)/2+1])/2; if(m1 == m2 ) { cout<<m1; return; } else { if(m1 > m2) median(a1, s1, (e1+s1)/2+1, a2, (e2+s2)/2, e2); else median(a1, (e1+s1)/2, e1, a2, s2, (e2+s2)/2+1); } } else { if(e1-s1 == 0) { m1 = (a1[s1]+a2[s2])/2; cout<<m1; return; } m1 = a1[(e1+s1)/2]; m2 = a2[(e2+s2)/2]; if(m1 == m2 ) { cout<<m1; return; } else { if(m1 > m2) median(a1, s1, (e1+s1)/2, a2, (e2+s2)/2, e2); else median(a1, (e1+s1)/2, e1, a2, s2, (e2+s2)/2); } } return; } int main() { int n1,n2,i; cout<<"\nEnter the number of elements for 1st array: "; cin>>n1; float a1[n1]; for(i = 0; i < n1; i++) { cout<<"Enter element for 1st array"<<i+1<<": "; cin>>a1[i]; } cout<<"\nEnter the number of elements for 2nd array: "; cin>>n2; float a2[n2]; for(i = 0; i < n2; i++) { cout<<"Enter element for 2nd array "<<i+1<<": "; cin>>a1[i]; } cout << "Median is "; median(a1, 0, n1-1, a2, 0, n2-1) ; return 0; }
ผลลัพธ์
Enter the number of elements for 1st array: 5 Enter element for 1st array1: 6 Enter element for 1st array2: 7 Enter element for 1st array3: 9 Enter element for 1st array4: 10 Enter element for 1st array5: 11 Enter the number of elements for 2nd array: 5 Enter element for 2nd array 1: 60 Enter element for 2nd array 2: 70 Enter element for 2nd array 3: 90 Enter element for 2nd array 4: 100 Enter element for 2nd array 5: 110 Median is 35
