In this approach we find the median of two given sorted arrays by:
Creating an array of length = length of given array1 + length of given array2.
Adding elements of both the arrays
Sorting the array using an inbuilt function (or merge sort)
Finding the median in O(1) depending on the length of the final ans array.
Implementation-
Let’s have a look at its implementation in Java -
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner s = new Scanner(System.in);
System.out.println("Enter size of array1 ");
int n = s.nextInt();
int[] arr1 = new int[n];
System.out.println("Enter integers in array1");
for (int i = 0; i < n; i++) {
arr1[i] = s.nextInt();
}
System.out.println("Enter size of array2 ");
int n1 = s.nextInt();
int[] arr2 = new int[n1];
System.out.println("Enter integers in array2");
for (int i = 0; i < n1; i++) {
arr2[i] = s.nextInt();
}
double ans = findMedianSortedArrays(arr1, arr2);
System.out.println("Median of Two Sorted Arrays: "+ ans);
}
public static double findMedianSortedArrays(int[] num1, int[] num2) {
// Creating array of len = sum of the lengths of both the arrays
int[] arr = new int[num1.length + num2.length];
// Adding all elements of 1st array
int j = 0;
for (int i = 0; i < num1.length; i++){
arr[j] = num1[i];
j++;
}
// Adding all elements of 2nd array
for (int i = 0; i <num2.length; i++){
arr[j] = num2[i];
j++;
}
// Sorting the array
Arrays.sort(arr);
// Finding median
double ans = 0;
if (arr.length % 2 == 0){
int midi1 = arr.length/2;
int midi2 = (arr.length/2) - 1;
ans = (arr[midi1] + arr[midi2]) / 2.0;
}
else{
int midindex = arr.length/2;
ans = arr[midindex];
}
return ans;
}
}
You can also try this code with Online Java Compiler
Time Complexity: O(M + N) as the time complexity is dominated via merge sort (sorting technique used even in built-in function - (Arrays.sort()) of java).
Space Complexity: O(M + M) as extra space for storing and creating an additional array of M + N size is being used.
where ‘M’ is the length of the first given sorted array and‘N’ is the length of the second given sorted array.
Approach 2 - Using Binary Search
The time and space complexity is optimised using Binary Search. Here, we divide into two cases - finding the median when sum (i.e., length of given array1 - A + length of given array2 - B) is odd and even and then adding them up.
After that we find the middle element of the A and B array and move towards the A and B array respectively depending on aMid(Middle element of A array) < bMid(Middle element of the B array) or vice versa.
Implementation-
Let’s have a look at its implementation in Java -
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner s = new Scanner(System.in);
System.out.println("Enter size of array1 ");
int n = s.nextInt();
int[] arr1 = new int[n];
System.out.println("Enter integers in array1");
for (int i = 0; i < n; i++) {
arr1[i] = s.nextInt();
}
System.out.println("Enter size of array2 ");
int n1 = s.nextInt();
int[] arr2 = new int[n1];
System.out.println("Enter integers in array2");
for (int i = 0; i < n1; i++) {
arr2[i] = s.nextInt();
}
double ans = findMedianSortedArrays(arr1, arr2);
System.out.println("Median of Two Sorted Arrays: "+ ans);
}
// Finding median of two given sorted arrays by Binary Search
public static double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
// Breaking total length into 2 parts and defining 2 possible medians
int left = (m + n + 1) / 2;
int right = (m + n + 2) / 2;
return (getkth(A, 0, B, 0, left) + getkth(A, 0, B, 0, right)) / 2.0;
}
public static double getkth(int[] A, int aStart, int[] B, int bStart, int k){
// Base Case
if (aStart > A.length - 1) return B[bStart + k - 1];
if (bStart > B.length - 1) return A[aStart + k - 1];
if (k == 1) return Math.min(A[aStart], B[bStart]);
// Finding middle element of A and B array
int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE;
if (aStart + k / 2 - 1 < A.length) aMid = A[aStart + k / 2 - 1];
if (bStart + k / 2 - 1 < B.length) bMid = B[bStart + k / 2 - 1];
// Checking aRight + bLeft
if (aMid < bMid) {
return getkth(A, aStart + k / 2, B, bStart, k - k / 2);
}
// Checking bRight + aLeft
else{
return getkth(A, aStart, B, bStart + k/2, k - k/2);
}
}
}
You can also try this code with Online Java Compiler
Time Complexity: O(log(M + N)) as for finding median binary search is used on both the sorted arrays. Here, ‘M’ is the length of the first given sorted array and‘N’ is the length of the second given sorted array.
Space Complexity: O(1) as no extra space has been used.
Frequently Asked Questions-
1. What is the median?
Ans: Median, in statistics, is the middle value of the given list of data, when arranged in an order. The arrangement of data or observations can be done either in ascending order or descending order.
2. What is Binary Search? Explain.
Ans: In Computer Science, Binary Search is a method for finding a target element in a sorted array by repeatedly dividing the search interval in half.
3. Why is it called Binary Search?
Ans: It is called Binary Search as it follows a divide and conquer approach by repeatedly splitting the search space in 2 halfs. Hence, It is also called Dichotomic Search (literally: "that cuts in two")
4. What is merge sort?
Ans. Merge sort is the sorting technique that follows the divide and conquer approach. It divides the array into equal halves and then combines them in a sorted manner.
5. What are various sorting techniques?
Ans. The various sorting techniques available are radix sort, merge sort, heap sort, insertion sort etc.
In this blog, we learned various approaches to find the median of two sorted arrays problem.
Median of Two Sorted Arrays is a standard merge sort problem that is optimized via binary search.
First approach is via solving via Merge Sort - where we add all the elements of both the given sorted arrays in another array and then finally sort the entire array to calculate median.
In the second approach i.e., via Binary Search, we split the search interval in half in every interval following the divide and conquer approach, reducing the target element's search space. It works for sorted arrays only.
Its Best Case Time Complexity is O(log(M + N)), but Worst Case Time Complexity is O(M + N), where ‘M’ is the length of the first given sorted array and ‘N’ is the length of the second given sorted array.
Check out more blogs on different dp problems like LCS, Friends Pairing Problem to read more about these topics in detail. And if you liked this blog, share it with your friends!
309+ registered 
