How to find median of two sorted arrays in Java? Example Tutorial

Hello friends, we meet again on our journey of Java and the ocean of knowledge. I am sure you guys must be very excited about today's lesson as today we will deep dive into something that makes everyone's head scratch, yes, we will talk about a popular coding problem. So friends, get ready to scratch your head, learn something, code a few things, and use some of your grey cells (Agatha christie fans rejoicing in the back :p). So friends, today's topic is coding and we will take on one of the most famous and difficult problems. Today we will learn how to find the median of two sorted arrays. seems easy right? Wait a bit, I will make sure you learn something new and make it a bit of a challenge :D

So, what's the wait? Let's start!

So let's understand the problem first. It may sound like an easy problem, but the optimal implementation is a pretty hard one, especially if you have to find the median of two sorted arrays of different sizes or lengths. 

The problem [Median of Two Sorted Array]:

So let's understand the problem. The problem is actually simple. You are given two sorted arrays, and you need to get the median of that arrays combined. Simple right? No? no worries. let me explain this in a simpler piece, bit by bit.

Consider a single array with n elements. Now, if n is odd or even, there are different formulas for both. let's see them both.

• If n is even: median = array[n/2] (value of (n/2)nd element)
• if n is odd: median = ((array[(n-1)/2]) + (array[(n+1)/2])) / 2

Considering the above basic mathematical formulas, let's take an example and check how it works.

Let's say we have an array of length 6 {1,3,5,7,9,10} the median for this array would be array[6/2], that is, array[3], which is 7.

Similarly, considering an array of odd lengths, let's say of length 5 {2,3,4,6,7}, the median would be (array[4/2] + array[6/2])/2 which is 5.

So, after understanding what a median is mathematical, let's brainstorm over our problem and its solution. We are given two arrays, both are sorted, think for two minutes about the solution and then we will discuss.

2. Solution:

So, I hope you guys have brainstormed enough. Now, the first and the most obvious solution is that we merge the two arrays and then find the median using the above formulas. Seems simple right? Let's take a detailed look at the code and the implementation.

2.1 Code (Brute Force approach):

Here is the easiest or brute force way to solve this problem in Java. 

import java.util.Arrays;
import java.util.Scanner;

public class MedianOfTwoSortedArrays {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int sizeOfFirstArray = sc.nextInt();
        int sizeOfSecondArray = sc.nextInt();

        int[] firstArray = new int[sizeOfFirstArray];
        int[] secondArray = new int[sizeOfSecondArray];

        for(int i=0;i<sizeOfFirstArray;i++) {
            firstArray[i] = sc.nextInt();
        }

        for(int i=0;i<sizeOfSecondArray;i++) {
            secondArray[i] = sc.nextInt();
        }

        Arrays.sort(firstArray);
        Arrays.sort(secondArray);

        double median = findMedianSortedArrays(firstArray, secondArray);

        System.out.println("median of above two arrays is: "+median);
    }

    public static double findMedianSortedArrays(int[] firstArray, int[] secondArray) {
        int firstArrayLength = firstArray.length;
        int secondArrayLength = secondArray.length;

        int[] combinedArray = new int[firstArrayLength+secondArrayLength];
        int k=0;
        for(int i:firstArray) {
            combinedArray[k++] = i;
        }

        for(int i:secondArray) {
            combinedArray[k++] = i;
        }

        Arrays.sort(combinedArray);
        double median;
        if(combinedArray.length % 2 == 0) {
            median = combinedArray[combinedArray.length/2];
        } else {
            median = (combinedArray[(combinedArray.length-1) / 2] 
             + combinedArray[(combinedArray.length+1) / 2])/2;
        }

        return median;

    }

}

Output:

After observing the output, we can clearly see that this brute force implementation is simple and easy. But, it is costly! the time complexity will be O(nlog(n)) because we need to sort the merged array again! 

Also here n is the size of the combined array. Same for the space complexity. this is not what we want actually. The code is correct, but not exactly the most efficient solution. 

There are many solutions available for these questions out there, but we will now discuss a solution that is one of the most efficient solutions. So, let's see the code and then try to understand it.

Code (Efficient approach)

Now, this is a slight better approach to calculate the median of two sorted arrays in Java:

import java.util.Arrays;
import java.util.Scanner;

public class MedianOfTwoSortedArrays {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int sizeOfFirstArray = sc.nextInt();
        int sizeOfSecondArray = sc.nextInt();

        int[] firstArray = new int[sizeOfFirstArray];
        int[] secondArray = new int[sizeOfSecondArray];

        for(int i=0;i<sizeOfFirstArray;i++) {
            firstArray[i] = sc.nextInt();
        }

        for(int i=0;i<sizeOfSecondArray;i++) {
            secondArray[i] = sc.nextInt();
        }

        Arrays.sort(firstArray);
        Arrays.sort(secondArray);

        double median = findMedianSortedArrays(firstArray, secondArray);

        System.out.println("median of above two arrays is: "+median);
    }

    public static double findMedianSortedArrays(int[] a, int[] b) {
        if(a.length == 0 && b.length == 0) return 0.0;

        //consider a=[2], b=[]
        //if not swapped, bleft will be -ve hence this condition will fail:
        //bleft == 0 ? Integer.MIN_VALUE : b[bleft - 1]
        if(a.length > b.length) {
            int[] temp = a;
            a = b;
            b = temp;
        }

        int lo = 0, hi = a.length, total = a.length + b.length;
        while(lo <= hi) {
            int aleft = lo + (hi - lo) / 2;
            int bleft = (total + 1) / 2 - aleft;
            int maVal = aleft == 0 ? Integer.MIN_VALUE : a[aleft - 1];
            int mbVal = bleft == 0 ? Integer.MIN_VALUE : b[bleft - 1];
            int aVal = aleft == a.length ? Integer.MAX_VALUE : a[aleft];
            int bVal = bleft == b.length ? Integer.MAX_VALUE : b[bleft];
            if(maVal <= bVal && mbVal <= aVal) {
                double res = Math.max(maVal, mbVal);
                if(total % 2 == 0) {
                    res += Math.min(aVal, bVal);
                    res /= 2.0;
                }
                return res;
            }else if(maVal > bVal) {
                hi = aleft - 1;
            } else {
                lo = aleft + 1;
            }
        }
        return 0.0;
    }

}

Now, as we have seen the code, can you guys try to understand it? take 2 minutes time and try to understand it by performing a dry run on the code. (yes, grab a pen-paper :p)

So, let's understand it then.

• perform binary search on 'a' if 'a' has less elements than 'b' else swap 'a' & 'b' & continue binary search on 'a'
  
  
• aleft & bleft are boundary elements
  
  
• hi=a.length & not a.length-1. run this test case to understand better : a=[1,2] & b=[3,4] for hi boundaries
  
  
• len(a)+len(b) is odd, median=max(a[aleft-1],max[bleft-1])
  
  
• len(a)+len(b) is even, median=(max(a[aleft-1],max[bleft])+min(a[aleft],b[bleft])/2.0
  
  
• (int+int)/2 will result integer value hence divide by 2.0 & not 2
  
  
• as using aleft-1 & bleft-1 to calculate median for odd no. of total elements so add 1 to total like this: bleft=(total + 1)/2-aleft.The above steps would be enough to make you understand the code thoroughly.

That's all about the How to calculate the median of two sorted arrays in Java. This is an interesting problem and you should know how to solve this, especially if you're preparing for coding interviews. This also explores other algorithms like searching in a sorted array 

Other Data Structure and Algorithms Resources you may like

• 5 Free Courses to learn Algorithms in-depth (courses)
• 10 Algorithms books every Programmer should read (books)
• My favorite Free Algorithms and Data Structure Courses on FreeCodeCamp (courses)
• 30+ linked list interview questions with a solution (linked list)
• 30+ array-based interview questions for programmers (array)
• 75+ Coding Problems from Interviews (questions)
• 10 Free Courses to learn Data Structure and Algorithms (courses)
• 10 Books to Prepare Technical Programming/Coding Job Interviews (books)
• 10 Courses to Prepare for Programming Job Interviews (courses)
• 5 Websites for Coding Interview Preparation for FREE (websites)
• 100+ Data Structure and Algorithms Interview Questions (questions)
• 20+ String Coding Problems from Interviews (questions)
• 10 Coding Tips and 101 Coding Questions for Interviews (tips)
• 50+ Algorithm based Interview questions from HackerNoon (questions)
• Top 5 Data Structure and Algorithms Courses for Programmers (courses)

Thanks for reading this article so far. If you like this Array coding problem and my solution and explanation, then please share it with your friends and colleagues. If you have any questions or feedback, then please drop a note.

P. S. - If you are looking for a FREE course to learn Data Structure from scratch, you can also check out the Data Structures in Java for the Noobs course on Udemy. A complete guide to learning everything there is to know about data structures for free.

Now, it's time for  question for you, What is your favorite array coding exercise? reverse an array, find missing number in an array or this question? Do let me know in comments.