Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction-
2.
Approach1 - Using Merge Sort Approach
3.
Time and Space Complexity-
4.
Approach 2 - Using Binary Search
5.
Time and Space Complexity-
6.
Frequently Asked Questions-
7.
Key Takeaways-
Last Updated: Mar 27, 2024

Median of Two Sorted Arrays

Author Raksha Jain
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction-

 

Today, let’s learn about a famous and commonly asked Interview Problem, i.e., median of two sorted arrays. 

It is a famous and common problem that is solved using binary search in its most optimized version.  

 

Problem Statement: Given two sorted arrays a[] and b[], find the median of these two sorted arrays. 

 

Example: 

array1 = [2, 3, 4, 5, 6, 9] array2 = [0, 1, 2]

The combined array would be array = [0, 1, 2, 2, 3, 4, 5, 6, 9]. So, the median would be 3.  

 

Let's get started and learn various approaches to solve this problem.

Also see, Euclid GCD Algorithm 

 

Approach1 - Using Merge Sort Approach

 

In this approach we find the median of two given sorted arrays by:

  1. Creating an array of length = length of given array1 + length of given array2.
  2. Adding elements of both the arrays
  3. Sorting the array using an inbuilt function (or merge sort) 
  4. 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;
        
    }
}

 

Output:

 

Enter size of array1 
6
Enter integers in array1 
2 3 4 5 6 9
Enter size of array2 
3
Enter integers in array2
0 1 2
Median of Two Sorted Arrays: 3.0

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Time and Space Complexity-

 

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

 

Output:

 

Enter size of array1 
6
Enter integers in array1 
2 3 4 5 6 9
Enter size of array2 
3
Enter integers in array2
0 1 2
Median of Two Sorted Arrays: 3.0

 

Time and Space Complexity-

 

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. 

 

Key Takeaways-

  

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!

Recommended Problem - Merge K Sorted Arrays

Practice a variety of on Coding Ninjas Studio  platform where you can find questions asked in all big-tech giants.

 

Previous article
How to find the minimum capacity of the ship to ship packages within d days.
Next article
Longest Common Prefix using Divide and Conquer Algorithm
Live masterclass