二分探索アプローチを使用して2つのソートされた配列の中央値を見つけるC++プログラム

二分探索アプローチを使用して、2つのソートされた配列の中央値を見つけるC++プログラムを開発します。

アルゴリズム

Begin
   Function median() with both the arrays and the start and end indexes of each array, which have two arrays and their respective elements as argument.
      A) first calculate the array length as e1 - s1, here e1 nd s1 are the end and start indices.
      B) If the length is 2 or 1, calculate the median of arrays according to even or odd length, print the result.
      C) Check if both the individual medians are equal, if yes, then print the result.
      D) If above two conditions are true then check if m>m2 then the combined median will either be in first half of the first array or in the second half of the second array.
      E) If m1<m2 then the combined median will either be in second half of the first array or in the first half of the second array.
      F) Call median() recursively, with updated start and end indexes.
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