Posted on by Kalkicode
Code Array

Find median of two sorted arrays

The problem is to finding the median of two sorted arrays. The median is the middle element of a dataset when arranged in ascending order. This problem often arises in various applications, including statistics, computer science, and data analysis.

Problem Statement

Given two sorted arrays arr1 and arr2, we need to find the median of the combined array formed by merging both arrays.

Example

Let's understand this with an example:

  • Array 1: [1, 2, 10]
  • Array 2: [4, 15, 16]

The merged array after combining both arrays in sorted order is: [1, 2, 4, 10, 15, 16]. The median of this merged array is 7, which is the average of the middle elements 4 and 10.

Idea to Solve

To solve this problem efficiently, we can use a binary search-like approach. We're looking for the middle element in the combined sorted array, which means we need to find the element at the (s1 + s2) / 2-th position, where s1 is the size of the first array and s2 is the size of the second array. We'll keep track of two pointers, one for each array, and iteratively compare the elements at these pointers to determine the next element to include in the merged array.

Algorithm

  1. Initialize two pointers first and second to 0, indicating the current positions in arr1 and arr2 respectively.
  2. Initialize a counter to 0 to keep track of the number of elements visited.
  3. Initialize variables result and temp to store the current and previous result.
  4. Run a loop until the counter reaches (s1 + s2) / 2:
    • Update temp to the current value of result.
    • Compare the elements at arr1[first] and arr2[second].
    • Choose the smaller element and update result accordingly. Move the corresponding pointer.
    • Increment the counter.
  5. After the loop, if the total size is odd, result is the median.
  6. If the total size is even, the median is the average of result and temp.

Pseudocode

median(arr1, arr2, s1, s2):
    total_size = s1 + s2
    first = 0
    second = 0
    counter = 0
    result = 0
    temp = 0

    while counter <= total_size / 2:
        temp = result

        if first < s1 and second < s2:
            if arr1[first] < arr2[second]:
                result = arr1[first]
                first++
            else:
                result = arr2[second]
                second++
        else if first < s1:
            result = arr1[first]
            first++
        else:
            result = arr2[second]
            second++
        
        counter++

    if total_size % 2 != 0:
        print("Median:", result)
    else:
        print("Median Elements:", result, temp)
        median = (result + temp) / 2
        print("Median:", median)

Code Solution

// C Program 
// Find median of two sorted arrays
#include <stdio.h>

//Function which is display array elements
void display(int arr[], int size)
{
    for (int i = 0; i < size; ++i)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void median(int arr1[],int arr2[],int s1,int s2)
{

    int total_size = s1 + s2 ;

    //This two variables indicate index of arr1 and arr2
    int first = 0;
    
    int second = 0;

    //This variable are used to control loop
    int counter = 0;

    //This variables are used to store result
    int result = 0;
    int temp = 0;


    while(counter <= total_size/2)
    {
        //Get current calculated result
        temp = result;

        if(first < s1 && second <s2)
        {
            //When both array elemement exist

            if(arr1[first]<arr2[second])
            {
                //When first array element are small
                result = arr1[first];
                first++;
            }
            else
            {
                //When second array element are small
                result = arr2[second];
                second++;
            }
        }
        else if(first < s1)
        {
            result = arr1[first];
            first++;
        }
        else
        {
            result = arr2[second];
            second++;
        }
        counter++;
    }
    printf(" First Array : ");
    display(arr1,s1);
    printf(" Second Array : ");
    display(arr2,s2);
    if(total_size % 2 != 0)
    {
        //only one middle element are possible
        printf(" Median : %d \n\n",result);
    }
    else
    {
        //when two middle elements are possible
        printf(" Median Elements [%d %d]  \n",result,temp);

        result = (result + temp) /2 ;
        
        printf(" Median : %d \n\n",result);

    }

}

int main()
{
    //When provide similar size of array elements
    int a1[] = {1, 2, 10}; 
    int a2[] = {4, 15, 16}; 

    //Get the size of array
    int s1 = sizeof(a1) / sizeof(a1[0]); 
    int s2 = sizeof(a2) / sizeof(a2[0]); 

    median(a1,a2,s1,s2);


    //When given
    int a3[] = {3,11,14}; 
    int a4[] = {6, 7, 22, 24}; 
    //Get the size of array
    s1 = sizeof(a3) / sizeof(a3[0]); 
    s2 = sizeof(a4) / sizeof(a4[0]); 

    median(a3,a4,s1,s2);

    int a6[] = {-3,5,8,9}; 
    int a7[] = {-6,-5,-3,-1,9,13}; 

    //Get the size of array
    s1 = sizeof(a6) / sizeof(a6[0]); 
    s2 = sizeof(a7) / sizeof(a7[0]); 

    median(a6,a7,s1,s2);

    return 0;
}

Output

 First Array : 1 2 10
 Second Array : 4 15 16
 Median Elements [10 4]
 Median : 7

 First Array : 3 11 14
 Second Array : 6 7 22 24
 Median : 11

 First Array : -3 5 8 9
 Second Array : -6 -5 -3 -1 9 13
 Median Elements [5 -1]
 Median : 2

// Java Program
// Find median of two sorted arrays

class MyArray
{
	
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			System.out.print(" " + arr[i] );
		}
		System.out.print("\n");
	}
	//Find the median of given two sorted arrays
	public void median(int[] arr1, int[] arr2)
	{
		//Get the size of array
		int s1 = arr1.length;
		int s2 = arr2.length;
	
		//This two variables indicate index of arr1 and arr2
		int first = 0;
		int second = 0;
		//This variable are used to control loop
		int counter = 0;
		//This variables are used to store result
		int result = 0;
		int temp = 0;

		//Calculating median of given two sorted arrays 
		while (counter <= (s1+s2) / 2)
		{
			//Get current calculated result
			temp = result;
			if (first < s1 && second < s2)
			{
				//When both array elemement exist
				if (arr1[first] < arr2[second])
				{
					//When first array element are small
					result = arr1[first];
					first++;
				}
				else
				{
					//When second array element are small
					result = arr2[second];
					second++;
				}
			}
			else if (first < s1)
			{
				result = arr1[first];
				first++;
			}
			else
			{
				result = arr2[second];
				second++;
			}
			counter++;
		}

		System.out.print(" First Array : ");
		display(arr1, s1);
		System.out.print(" Second Array : ");
		display(arr2, s2);

		if ((s1+s2) % 2 != 0)
		{
			System.out.print(" Median : " + result + " \n\n");
		}
		else
		{
			System.out.print(" Median Elements [" + result + " " + temp + "] \n");
			result = (result + temp) / 2;
			System.out.print(" Median : " + result + " \n\n");
		}
	}
	public static void main(String[] args)
	{
		MyArray obj = new MyArray();
		//When provide similar size of array elements
		int[] a1 = {1 , 2 , 10};
		int[] a2 = {4 , 15 , 16};
	
		obj.median(a1, a2);
		//When given
		int[] a3 =  { 3 , 11 , 14 };
		int[] a4 =  { 6 , 7 , 22 , 24 };
		
		obj.median(a3, a4);
		
		int[] a6 = {-3 , 5 , 8 , 9};
		int[] a7 =  {-6 , -5 , -3 , -1 , 9 , 13};
		
		obj.median(a6, a7);
	}
}

Output

 First Array :  1 2 10
 Second Array :  4 15 16
 Median Elements [10 4]
 Median : 7

 First Array :  3 11 14
 Second Array :  6 7 22 24
 Median : 11

 First Array :  -3 5 8 9
 Second Array :  -6 -5 -3 -1 9 13
 Median Elements [5 -1]
 Median : 2

//Include header file
#include <iostream>

using namespace std;
// C++ Program
// Find median of two sorted arrays
class MyArray
{
    public:
        //Function which is display array elements
        void display(int arr[], int size)
        {
            for (int i = 0; i < size; ++i)
            {
                cout << " " << arr[i];
            }
            cout << "\n";
        }
    //Find the median of given two sorted arrays
    void median(int arr1[], int arr2[],int s1,int s2)
    {

        //This two variables indicate index of arr1 and arr2
        int first = 0;
        int second = 0;
        //This variable are used to control loop
        int counter = 0;
        //This variables are used to store result
        int result = 0;
        int temp = 0;
        //Calculating median of given two sorted arrays 
        while (counter <= (s1 + s2) / 2)
        {
            //Get current calculated result
            temp = result;
            if (first < s1 && second < s2)
            {
                //When both array elemement exist
                if (arr1[first] < arr2[second])
                {
                    //When first array element are small
                    result = arr1[first];
                    first++;
                }
                else
                {
                    //When second array element are small
                    result = arr2[second];
                    second++;
                }
            }
            else if (first < s1)
            {
                result = arr1[first];
                first++;
            }
            else
            {
                result = arr2[second];
                second++;
            }
            counter++;
        }
        cout << " First Array : ";
        this->display(arr1, s1);
        cout << " Second Array : ";
        this->display(arr2, s2);
        if ((s1 + s2) % 2 != 0)
        {
            cout << " Median : " << result << " \n\n";
        }
        else
        {
            cout << " Median Elements [" << result << " " << temp << "] \n";
            result = (result + temp) / 2;
            cout << " Median : " << result << " \n\n";
        }
    }
};
int main()
{
    MyArray obj = MyArray();
    //When provide similar size of array elements
    int a1[] = {1, 2, 10}; 
    int a2[] = {4, 15, 16}; 

    //Get the size of array
    int s1 = sizeof(a1) / sizeof(a1[0]); 
    int s2 = sizeof(a2) / sizeof(a2[0]); 

    obj.median(a1,a2,s1,s2);


    //When given
    int a3[] = {3,11,14}; 
    int a4[] = {6, 7, 22, 24}; 
    //Get the size of array
    s1 = sizeof(a3) / sizeof(a3[0]); 
    s2 = sizeof(a4) / sizeof(a4[0]); 

    obj.median(a3,a4,s1,s2);

    int a6[] = {-3,5,8,9}; 
    int a7[] = {-6,-5,-3,-1,9,13}; 

    //Get the size of array
    s1 = sizeof(a6) / sizeof(a6[0]); 
    s2 = sizeof(a7) / sizeof(a7[0]); 

    obj.median(a6,a7,s1,s2);

    return 0;
}

Output

 First Array :  1 2 10
 Second Array :  4 15 16
 Median Elements [10 4]
 Median : 7

 First Array :  3 11 14
 Second Array :  6 7 22 24
 Median : 11

 First Array :  -3 5 8 9
 Second Array :  -6 -5 -3 -1 9 13
 Median Elements [5 -1]
 Median : 2

//Include namespace system
using System;
// C# Program
// Find median of two sorted arrays
class MyArray
{
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	//Find the median of given two sorted arrays
	public void median(int[] arr1, int[] arr2)
	{
		//Get the size of array
		int s1 = arr1.Length;
		int s2 = arr2.Length;
		//This two variables indicate index of arr1 and arr2
		int first = 0;
		int second = 0;
		//This variable are used to control loop
		int counter = 0;
		//This variables are used to store result
		int result = 0;
		int temp = 0;
		//Calculating median of given two sorted arrays 
		while (counter <= (s1 + s2) / 2)
		{
			//Get current calculated result
			temp = result;
			if (first < s1 && second < s2)
			{
				//When both array elemement exist
				if (arr1[first] < arr2[second])
				{
					//When first array element are small
					result = arr1[first];
					first++;
				}
				else
				{
					//When second array element are small
					result = arr2[second];
					second++;
				}
			}
			else if (first < s1)
			{
				result = arr1[first];
				first++;
			}
			else
			{
				result = arr2[second];
				second++;
			}
			counter++;
		}
		Console.Write(" First Array : ");
		display(arr1, s1);
		Console.Write(" Second Array : ");
		display(arr2, s2);
		if ((s1 + s2) % 2 != 0)
		{
			Console.Write(" Median : " + result + " \n\n");
		}
		else
		{
			Console.Write(" Median Elements [" + result + " " + temp + "] \n");
			result = (result + temp) / 2;
			Console.Write(" Median : " + result + " \n\n");
		}
	}
	public static void Main(String[] args)
	{
		MyArray obj = new MyArray();
		int[] a1 = {
			1 , 2 , 10
		};
		int[] a2 = {
			4 , 15 , 16
		};
		obj.median(a1, a2);
		int[] a3 = {
			3 , 11 , 14
		};
		int[] a4 = {
			6 , 7 , 22 , 24
		};
		obj.median(a3, a4);
		int[] a6 = {
			-3 , 5 , 8 , 9
		};
		int[] a7 = {
			-6 , -5 , -3 , -1 , 9 , 13
		};
		obj.median(a6, a7);
	}
}

Output

 First Array :  1 2 10
 Second Array :  4 15 16
 Median Elements [10 4]
 Median : 7

 First Array :  3 11 14
 Second Array :  6 7 22 24
 Median : 11

 First Array :  -3 5 8 9
 Second Array :  -6 -5 -3 -1 9 13
 Median Elements [5 -1]
 Median : 2

<?php
// Php Program
// Find median of two sorted arrays
class MyArray
{
	//Function which is display array elements
	public	function display( $arr, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo " ". $arr[$i];
		}
		echo "\n";
	}
	//Find the median of given two sorted arrays
	public	function median( $arr1, & $arr2)
	{
		//Get the size of array
		$s1 = count($arr1);
		$s2 = count($arr2);
		//This two variables indicate index of arr1 and arr2
		$first = 0;
		$second = 0;
		//This variable are used to control loop
		$counter = 0;
		//This variables are used to store result
		$result = 0;
		$temp = 0;
		//Calculating median of given two sorted arrays 
		while ($counter <= intval(($s1 + $s2) / 2))
		{
			//Get current calculated result
			$temp = $result;
			if ($first < $s1 && $second < $s2)
			{
				//When both array elemement exist
				if ($arr1[$first] < $arr2[$second])
				{
					//When first array element are small
					$result = $arr1[$first];
					$first++;
				}
				else
				{
					//When second array element are small
					$result = $arr2[$second];
					$second++;
				}
			}
			else if ($first < $s1)
			{
				$result = $arr1[$first];
				$first++;
			}
			else
			{
				$result = $arr2[$second];
				$second++;
			}
			$counter++;
		}
		echo " First Array : ";
		$this->display($arr1, $s1);
		echo " Second Array : ";
		$this->display($arr2, $s2);
		if (($s1 + $s2) % 2 != 0)
		{
			echo " Median : ". $result ." \n\n";
		}
		else
		{
			echo " Median Elements [". $result ." ". $temp ."] \n";
			$result = intval(($result + $temp) / 2);
			echo " Median : ". $result ." \n\n";
		}
	}
}

function main()
{
	$obj = new MyArray();
	//When provide similar size of array elements
	$a1 = array(1, 2, 10);
	$a2 = array(4, 15, 16);
	$obj->median($a1, $a2);
	//When given
	$a3 = array(3, 11, 14);
	$a4 = array(6, 7, 22, 24);
	$obj->median($a3, $a4);
	$a6 = array(-3, 5, 8, 9);
	$a7 = array(-6, -5, -3, -1, 9, 13);
	$obj->median($a6, $a7);
}
main();

Output

 First Array :  1 2 10
 Second Array :  4 15 16
 Median Elements [10 4]
 Median : 7

 First Array :  3 11 14
 Second Array :  6 7 22 24
 Median : 11

 First Array :  -3 5 8 9
 Second Array :  -6 -5 -3 -1 9 13
 Median Elements [5 -1]
 Median : 2

// Node Js Program
// Find median of two sorted arrays
class MyArray
{
	//Function which is display array elements
	display(arr, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	//Find the median of given two sorted arrays
	median(arr1, arr2)
	{
		//Get the size of array
		var s1 = arr1.length;
		var s2 = arr2.length;
		//This two variables indicate index of arr1 and arr2
		var first = 0;
		var second = 0;
		//This variable are used to control loop
		var counter = 0;
		//This variables are used to store result
		var result = 0;
		var temp = 0;
		//Calculating median of given two sorted arrays 
		while (counter <= parseInt((s1 + s2) / 2))
		{
			//Get current calculated result
			temp = result;
			if (first < s1 && second < s2)
			{
				//When both array elemement exist
				if (arr1[first] < arr2[second])
				{
					//When first array element are small
					result = arr1[first];
					first++;
				}
				else
				{
					//When second array element are small
					result = arr2[second];
					second++;
				}
			}
			else if (first < s1)
			{
				result = arr1[first];
				first++;
			}
			else
			{
				result = arr2[second];
				second++;
			}
			counter++;
		}
		process.stdout.write(" First Array : ");
		this.display(arr1, s1);
		process.stdout.write(" Second Array : ");
		this.display(arr2, s2);
		if ((s1 + s2) % 2 != 0)
		{
			process.stdout.write(" Median : " + result + " \n\n");
		}
		else
		{
			process.stdout.write(" Median Elements [" + result + " " + temp + "] \n");
			result = parseInt((result + temp) / 2);
			process.stdout.write(" Median : " + result + " \n\n");
		}
	}
}

function main()
{
	var obj = new MyArray();
	//When provide similar size of array elements
	var a1 = [1, 2, 10];
	var a2 = [4, 15, 16];
	obj.median(a1, a2);
	//When given
	var a3 = [3, 11, 14];
	var a4 = [6, 7, 22, 24];
	obj.median(a3, a4);
	var a6 = [-3, 5, 8, 9];
	var a7 = [-6, -5, -3, -1, 9, 13];
	obj.median(a6, a7);
}
main();

Output

 First Array :  1 2 10
 Second Array :  4 15 16
 Median Elements [10 4]
 Median : 7

 First Array :  3 11 14
 Second Array :  6 7 22 24
 Median : 11

 First Array :  -3 5 8 9
 Second Array :  -6 -5 -3 -1 9 13
 Median Elements [5 -1]
 Median : 2

#  Python 3 Program
#  Find median of two sorted arrays
class MyArray :
	# Function which is display array elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	
	# Find the median of given two sorted arrays
	def median(self, arr1, arr2) :
		# Get the size of array
		s1 = len(arr1)
		s2 = len(arr2)
		# This two variables indicate index of arr1 and arr2
		first = 0
		second = 0
		# This variable are used to control loop
		counter = 0
		# This variables are used to store result
		result = 0
		temp = 0
		# Calculating median of given two sorted arrays 
		while (counter <= int((s1 + s2) / 2)) :
			# Get current calculated result
			temp = result
			if (first < s1 and second < s2) :
				# When both array elemement exist
				if (arr1[first] < arr2[second]) :
					# When first array element are small
					result = arr1[first]
					first += 1
				else :
					# When second array element are small
					result = arr2[second]
					second += 1
				
			
			elif(first < s1) :
				result = arr1[first]
				first += 1
			else :
				result = arr2[second]
				second += 1
			
			counter += 1
		
		print(" First Array : ", end = "")
		self.display(arr1, s1)
		print(" Second Array : ", end = "")
		self.display(arr2, s2)
		if ((s1 + s2) % 2 != 0) :
			print(" Median : ", result ," \n\n", end = "")
		else :
			print(" Median Elements [", result ," ", temp ,"] \n", end = "")
			result = int((result + temp) / 2)
			print(" Median : ", result ," \n\n", end = "")
		
	

def main() :
	obj = MyArray()
	# When provide similar size of array elements
	a1 = [1, 2, 10]
	a2 = [4, 15, 16]
	obj.median(a1, a2)
	# When given
	a3 = [3, 11, 14]
	a4 = [6, 7, 22, 24]
	obj.median(a3, a4)
	a6 = [-3, 5, 8, 9]
	a7 = [-6, -5, -3, -1, 9, 13]
	obj.median(a6, a7)

if __name__ == "__main__": main()

Output

 First Array :   1  2  10
 Second Array :   4  15  16
 Median Elements [ 10   4 ]
 Median :  7

 First Array :   3  11  14
 Second Array :   6  7  22  24
 Median :  11

 First Array :   -3  5  8  9
 Second Array :   -6  -5  -3  -1  9  13
 Median Elements [ 5   -1 ]
 Median :  2

#  Ruby Program
#  Find median of two sorted arrays
class MyArray

	# Function which is display array elements
	def display(arr, size)
	
		i = 0
		while (i < size)
		
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
	# Find the median of given two sorted arrays
	def median(arr1, arr2)
	
		# Get the size of array
		s1 = arr1.length
		s2 = arr2.length
		# This two variables indicate index of arr1 and arr2
		first = 0
		second = 0
		# This variable are used to control loop
		counter = 0
		# This variables are used to store result
		result = 0
		temp = 0
		# Calculating median of given two sorted arrays 
		while (counter <= (s1 + s2) / 2)
		
			# Get current calculated result
			temp = result
			if (first < s1 && second < s2)
			
				# When both array elemement exist
				if (arr1[first] < arr2[second])
				
					# When first array element are small
					result = arr1[first]
					first += 1
				else
				
					# When second array element are small
					result = arr2[second]
					second += 1
				end
			elsif(first < s1)
			
				result = arr1[first]
				first += 1
			else
			
				result = arr2[second]
				second += 1
			end
			counter += 1
		end
		print(" First Array : ")
		self.display(arr1, s1)
		print(" Second Array : ")
		self.display(arr2, s2)
		if ((s1 + s2) % 2 != 0)
		
			print(" Median : ", result ," \n\n")
		else
		
			print(" Median Elements [", result ," ", temp ,"] \n")
			result = (result + temp) / 2
			print(" Median : ", result ," \n\n")
		end
	end
end
def main()

	obj = MyArray.new()
	# When provide similar size of array elements
	a1 = [1, 2, 10]
	a2 = [4, 15, 16]
	obj.median(a1, a2)
	# When given
	a3 = [3, 11, 14]
	a4 = [6, 7, 22, 24]
	obj.median(a3, a4)
	a6 = [-3, 5, 8, 9]
	a7 = [-6, -5, -3, -1, 9, 13]
	obj.median(a6, a7)
end
main()

Output

 First Array :  1 2 10
 Second Array :  4 15 16
 Median Elements [10 4] 
 Median : 7 

 First Array :  3 11 14
 Second Array :  6 7 22 24
 Median : 11 

 First Array :  -3 5 8 9
 Second Array :  -6 -5 -3 -1 9 13
 Median Elements [5 -1] 
 Median : 2 


// Scala Program
// Find median of two sorted arrays
class MyArray
{
	//Function which is display array elements
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	//Find the median of given two sorted arrays
	def median(arr1: Array[Int], arr2: Array[Int]): Unit = {
		//Get the size of array
		var s1: Int = arr1.length;
		var s2: Int = arr2.length;
		//This two variables indicate index of arr1 and arr2
		var first: Int = 0;
		var second: Int = 0;
		//This variable are used to control loop
		var counter: Int = 0;
		//This variables are used to store result
		var result: Int = 0;
		var temp: Int = 0;
		//Calculating median of given two sorted arrays 
		while (counter <= ((s1 + s2) / 2).toInt)
		{
			//Get current calculated result
			temp = result;
			if (first < s1 && second < s2)
			{
				//When both array elemement exist
				if (arr1(first) < arr2(second))
				{
					//When first array element are small
					result = arr1(first);
					first += 1;
				}
				else
				{
					//When second array element are small
					result = arr2(second);
					second += 1;
				}
			}
			else if (first < s1)
			{
				result = arr1(first);
				first += 1;
			}
			else
			{
				result = arr2(second);
				second += 1;
			}
			counter += 1;
		}
		print(" First Array : ");
		display(arr1, s1);
		print(" Second Array : ");
		display(arr2, s2);
		if ((s1 + s2) % 2 != 0)
		{
			print(" Median : " + result + " \n\n");
		}
		else
		{
			print(" Median Elements [" + result + " " + temp + "] \n");
			result = ((result + temp) / 2).toInt;
			print(" Median : " + result + " \n\n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyArray = new MyArray();
		//When provide similar size of array elements
		var a1: Array[Int] = Array(1, 2, 10);
		var a2: Array[Int] = Array(4, 15, 16);
		obj.median(a1, a2);
		//When given
		var a3: Array[Int] = Array(3, 11, 14);
		var a4: Array[Int] = Array(6, 7, 22, 24);
		obj.median(a3, a4);
		var a6: Array[Int] = Array(-3, 5, 8, 9);
		var a7: Array[Int] = Array(-6, -5, -3, -1, 9, 13);
		obj.median(a6, a7);
	}
}

Output

 First Array :  1 2 10
 Second Array :  4 15 16
 Median Elements [10 4]
 Median : 7

 First Array :  3 11 14
 Second Array :  6 7 22 24
 Median : 11

 First Array :  -3 5 8 9
 Second Array :  -6 -5 -3 -1 9 13
 Median Elements [5 -1]
 Median : 2

// Swift Program
// Find median of two sorted arrays
class MyArray
{
	//Function which is display array elements
	func display(_ arr: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
	//Find the median of given two sorted arrays
	func median(_ arr1: [Int], _ arr2: [Int])
	{
		//Get the size of array
		let s1: Int = arr1.count;
		let s2: Int = arr2.count;
		//This two variables indicate index of arr1 and arr2
		var first: Int = 0;
		var second: Int = 0;
		//This variable are used to control loop
		var counter: Int = 0;
		//This variables are used to store result
		var result: Int = 0;
		var temp: Int = 0;
		//Calculating median of given two sorted arrays 
		while (counter <= (s1 + s2) / 2)
		{
			//Get current calculated result
			temp = result;
			if (first < s1 && second < s2)
			{
				//When both array elemement exist
				if (arr1[first] < arr2[second])
				{
					//When first array element are small
					result = arr1[first];
					first += 1;
				}
				else
				{
					//When second array element are small
					result = arr2[second];
					second += 1;
				}
			}
			else if (first < s1)
			{
				result = arr1[first];
				first += 1;
			}
			else
			{
				result = arr2[second];
				second += 1;
			}
			counter += 1;
		}
		print(" First Array : ", terminator: "");
		self.display(arr1, s1);
		print(" Second Array : ", terminator: "");
		self.display(arr2, s2);
		if ((s1 + s2) % 2 != 0)
		{
			print(" Median : ", result ," \n\n", terminator: "");
		}
		else
		{
			print(" Median Elements [", result ," ", temp ,"] \n", terminator: "");
			result = (result + temp) / 2;
			print(" Median : ", result ," \n\n", terminator: "");
		}
	}
}
func main()
{
	let obj: MyArray = MyArray();
	//When provide similar size of array elements
	let a1: [Int] = [1, 2, 10];
	let a2: [Int] = [4, 15, 16];
	obj.median(a1, a2);
	//When given
	let a3: [Int] = [3, 11, 14];
	let a4: [Int] = [6, 7, 22, 24];
	obj.median(a3, a4);
	let a6: [Int] = [-3, 5, 8, 9];
	let a7: [Int] = [-6, -5, -3, -1, 9, 13];
	obj.median(a6, a7);
}
main();

Output

 First Array :   1  2  10
 Second Array :   4  15  16
 Median Elements [ 10   4 ]
 Median :  7

 First Array :   3  11  14
 Second Array :   6  7  22  24
 Median :  11

 First Array :   -3  5  8  9
 Second Array :   -6  -5  -3  -1  9  13
 Median Elements [ 5   -1 ]
 Median :  2

Output Explanation

For the given examples and code, the output is as follows:

  1. [1, 2, 10] and [4, 15, 16]:

    • Merged Array: [1, 2, 4, 10, 15, 16]
    • Median Elements: 10 and 4
    • Median: (10 + 4) / 2 = 7

  2. [3, 11, 14] and [6, 7, 22, 24]:

    • Merged Array: [3, 6, 7, 11, 14, 22, 24]
    • Median: 11

  3. [-3, 5, 8, 9] and [-6, -5, -3, -1, 9, 13]:

    • Merged Array: [-6, -5, -3, -3, -1, 5, 8, 9, 9, 13]
    • Median Elements: 5 and -1
    • Median: (5 + -1) / 2 = 2

Time Complexity

The time complexity of this algorithm is O((s1 + s2)/2), which simplifies to O(n), where n is the total number of elements in both arrays. This is because in the worst case, the algorithm iterates through all elements once.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment





Categories
Relative Post