C++ Program to Find the Median of Two Sorted Arrays using Binary Search

This is a C++ program to find the median of two sorted arrays using binary search approach.

Problem Description

1. This algorithm finds the median of two sorted arrays using binary search approach.
2. The time complexity of this algorithm is O(log(n)).

Problem Solution

1. This algorithm takes the input of ‘n’ data elements of both the arrays.
2. Using decrease and conquer method find the combined median of the data arrays.
3. Exit.

Program/Source Code

C++ Program to find the median of two sorted arrays using binary search approach.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#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;
}

Program Explanation

1. Take the input of the arrays of ‘n’ data element.
2. Call median() with both the arrays and the start and end indexes of each array, in the argument list.
3. Inside median(), first calculate the array length as ‘e1-s1’.
4. If the length is 2 or 1 calculate the median of arrays according to even or odd length, print the result and return to main.
5. Check if both the individual medians are equal, if yes, then print the result and return to main.
6. Otherwise, check if med1>med2 then the combined median will either be in first half of the first array or in the second half of the second array.
7. So call median() recursively, with updated start and end indexes.
8. If med1<med2 then the combined median will either be in second half of the first array or in the first half of the second array.
9. So call median() recursively, with updated start and end indexes.
10. Exit.

Runtime Test Cases

Case 1:
Enter the length of the arrays: 4
 
Enter the first sorted sequence :
Enter 1 value: 2
Enter 2 value: 4
Enter 3 value: 6
Enter 4 value: 8
 
Enter the second sorted sequence :
Enter 1 value: 1
Enter 2 value: 3
Enter 3 value: 5
Enter 4 value: 7
 
the median of the arrays is: 4.5
 
Case 2:
Enter the length of the arrays: 5
 
Enter the first sorted sequence :
Enter 1 value: 1
Enter 2 value: 3
Enter 3 value: 5
Enter 4 value: 7
Enter 5 value: 9
 
Enter the second sorted sequence :
Enter 1 value: 0
Enter 2 value: 2
Enter 3 value: 4
Enter 4 value: 6
Enter 5 value: 8
 
the median of the arrays is: 4.5

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Perform Integer Partition for a Specific Case

» Next - C++ Program to Perform Edge Coloring to the Line Graph of an Input Graph

Related Posts:

Recommended Articles: