Median of Two Sorted Arrays GFG Solution in Java

Given two sorted arrays of sizes N and M respectively. The task is to find the median of the two arrays when they get merged.
If there are even number of elements in the resulting array, find the floor of the average of two medians.

Example 1:

Input:
N = 5, M = 6 
arr[] = {1,2,3,4,5}
brr[] = {3,4,5,6,7,8}
Output: 4

This Java code implements the solution to the “Median of Two Sorted Arrays” problem, where we need to find the median of two sorted arrays after they are merged.

Algorithm:

  1. Initialize the lower and upper bounds of the first array as 0 and m respectively, where m is the size of the first array.
  2. While the lower bound is less than or equal to the upper bound: a. Find the mid-index of the first array as (low+high)/2, and the corresponding index of the second array as ((m+n+1)/2)-i1, where n is the size of the second array. b. Find the minimum and maximum elements of the left and right halves of the two arrays, taking into account the mid-indices found in step 2a. c. If the maximum element of the left half of the first array is less than or equal to the minimum element of the right half of the second array, and the maximum element of the left half of the second array is less than or equal to the minimum element of the right half of the first array, then we have found the median.
    • If the sum of the lengths of the two arrays is even, then the median is the average of the maximum of the left halves and the minimum of the right halves.
    • Otherwise, the median is the maximum of the maximums of the left halves. d. If the maximum element of the left half of the first array is greater than the minimum element of the right half of the second array, then we need to move the mid-index of the first array to the left (i.e. update the upper bound). e. Otherwise, we need to move the mid-index of the first array to the right (i.e. update the lower bound).
  3. If we haven’t found the median after the loop, return -1 (this should never happen if the inputs are valid).

Note:

  • If the size of the first array is greater than the size of the second array, we swap the two arrays to ensure that the first array is always the smaller one.

Median of Two Sorted Arrays GFG Solution in Java:

//Median of Two Sorted Arrays GFG Solution in Java

//User function Template for Java

class Solution
{
    //Function to find the median of the two arrays when they get merged.
    public static int findMedian(int arr[], int m, int brr[], int n)
    {
        
       // if(n>m) return findMedian(brr,m,arr,n);
       if(m>n) return findMedian(brr,n,arr,m);
       int low = 0, high = m;

		while(low <= high)
		{
			int i1 = (low + high) / 2;
			int i2 = ((m + n + 1) / 2 )- i1;

			int min1 = (i1 == m)?Integer.MAX_VALUE:arr[i1];
			int max1 = (i1 == 0)?Integer.MIN_VALUE:arr[i1 - 1];
			
			int min2 = (i2 == n)?Integer.MAX_VALUE:brr[i2];
			int max2 = (i2 == 0)?Integer.MIN_VALUE:brr[i2 - 1];

			if(max1 <= min2 && max2 <= min1)
			{
				if((m + n) % 2 == 0)
					return (Math.max(max1, max2) + Math.min(min1, min2)) / 2;
				else
					return Math.max(max1, max2);
			}
			else if(max1 > min2)
				high = i1 - 1;
			else 
				low = i1 + 1;
		}
		
		return -1;
       
        
    }
}

Disclaimer: This problem(Median of Two Sorted Arrays) is originally created by GeeksforGeeksCodesagar only provides a solution for it. This solution is only for Educational and learning purposes.

Leave a Comment