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
- Initialize two pointers
first
andsecond
to 0, indicating the current positions inarr1
andarr2
respectively. - Initialize a counter to 0 to keep track of the number of elements visited.
- Initialize variables
result
andtemp
to store the current and previous result. - Run a loop until the counter reaches
(s1 + s2) / 2
:- Update
temp
to the current value ofresult
. - Compare the elements at
arr1[first]
andarr2[second]
. - Choose the smaller element and update
result
accordingly. Move the corresponding pointer. - Increment the counter.
- Update
- After the loop, if the total size is odd,
result
is the median. - If the total size is even, the median is the average of
result
andtemp
.
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, 2, 10]
and[4, 15, 16]
:- Merged Array:
[1, 2, 4, 10, 15, 16]
- Median Elements:
10
and4
- Median:
(10 + 4) / 2 = 7
- Merged Array:
-
[3, 11, 14]
and[6, 7, 22, 24]
:- Merged Array:
[3, 6, 7, 11, 14, 22, 24]
- Median:
11
- Merged Array:
-
[-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
- Merged Array:
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.
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