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);
int s2 = sizeof(a2) / sizeof(a2);

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);
s2 = sizeof(a4) / sizeof(a4);

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);
s2 = sizeof(a7) / sizeof(a7);

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);
int s2 = sizeof(a2) / sizeof(a2);

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);
s2 = sizeof(a4) / sizeof(a4);

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);
s2 = sizeof(a7) / sizeof(a7);

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.

Categories
Relative Post