C++ Programming Code Examples C++ > Sorting Searching Code Examples Find the Median of two Sorted Arrays using Binary Search Approach Find the Median of two Sorted Arrays using Binary Search Approach - This algorithm finds the median of two sorted arrays using binary search approach. - The time complexity of this algorithm is O(log(n)). - This algorithm takes the input of 'n' data elements of both the arrays. - Using decrease and conquer method find the combined median of the data arrays. - Exit. #include<iostream> using namespace std; // Function to find the median of two sorted array of equal length. void median(float arr1[], int s1, int e1, float arr2[], int s2, int e2) { float med1, med2; // If the length of the sub arrays is even. if((e1-s1+1)%2 == 0) { // If only two element left in the array then the median can be found. if(e1-s1 == 1) { // median of the array will be the average of the maximum of the smaller elements and minimum of the greater element. med1 = ((arr1[s1]<arr2[s2]?arr1[s1]:arr2[s2])+(arr1[e1]>arr2[e2]?arr1[e1]:arr2[e2]))/2; cout<<med1; return; } // If more element are there then the individual median will be the average of mid data element of each array. med1 = (arr1[(e1+s1)/2]+arr1[(e1+s1)/2+1])/2; med2 = (arr2[(e2+s2)/2]+arr2[(e2+s2)/2+1])/2; // If the calculated individual medians are equal then the combined median will also be same. if(med1 == med2 ) { cout<<med1; return; } else { // If median of the first array is greater than the second one then- // The combined median will be either in the first half of the first array or in the second half of the other array. if(med1 > med2) median(arr1, s1, (e1+s1)/2+1, arr2, (e2+s2)/2, e2); // Otherwise the combined median will be either in second half of first array or in the first half of the other array. else median(arr1, (e1+s1)/2, e1, arr2, s2, (e2+s2)/2+1); } } // If the length of the sub array is odd. else { if(e1-s1 == 0) { med1 = (arr1[s1]+arr2[s2])/2; cout<<med1; return; } // If more element are there then the individual median will be the mid data element of each array. med1 = arr1[(e1+s1)/2]; med2 = arr2[(e2+s2)/2]; // If the calculated individual medians are equal then the combined median will also be same. if(med1 == med2 ) { cout<<med1; return; } else { // If median of the first array is greater than the second one then- // The combined median will be either in the first half of the first array or in the second half of the other array. if(med1 > med2) median(arr1, s1, (e1+s1)/2, arr2, (e2+s2)/2, e2); // Otherwise the combined median will be either in second half of first array or in the first half of the other array. else median(arr1, (e1+s1)/2, e1, arr2, s2, (e2+s2)/2); } } return; } int main() { int n, i; cout<<"Enter the length of the arrays: "; cin>>n; float arr1[n], arr2[n]; // Take the input of second sequence. cout<<"\nEnter the first sorted sequence :\n"; for(i = 0; i < n; i++) { cout<<"Enter "<<i+1<<" value: "; cin>>arr1[i]; } // Take the input of second sequence. cout<<"\nEnter the second sorted sequence :\n"; for(i = 0; i < n; i++) { cout<<"Enter "<<i+1<<" value: "; cin>>arr2[i]; } // Print the combined array. cout<<"\n\nthe median of the arrays is: "; median(arr1, 0, n-1, arr2, 0, n-1); return 0; }