Array

Median of two sorted array

Pinterest LinkedIn Tumblr

There are two sorted arrays A and B of size M and N respectively. Find the median of the two sorted arrays. Write a program to implement median of Two Sorted Arrays.

Algorithm Explanation

Initialize two arrays and Pass to the utility function.
The utility function takes middle element of each array. If array 1 middle element greater than array2, call the function recursively with array1, lower1, middle1, array2, mdiile2 and heigh2.
Otherwise, call the function recursively using array1, middle1, high1, array2, low2 and moiddle2 arguments.
The utility function returns an array of medium elements and prints the values.

Source Code

package com.dsacode.DataStructre.array;
 
import java.util.Arrays;
 
public class MedianOfTwoSortedArrays {
 
    public static int median(int[] arr1, int[] arr2) {
        int N = arr1.length;
        return median(arr1, 0, N -1 , arr2, 0, N - 1);
    }
     
    public static int median(int[] arr1, int l1, int h1, int[] arr2, int l2, int h2)  {
        int mid1 = (h1 + l1 ) / 2;
        int mid2 = (h2 + l2 ) / 2;
 
        if (h1 - l1 == 1)
            return (Math.max(arr1[l1] , arr2[l2]) + Math.min(arr1[h1] , arr2[h2]))/2;
        else if (arr1[mid1] > arr2[mid2])
            return median(arr1, l1, mid1 , arr2, mid2 , h2);   
        else
            return median(arr1, mid1 , h1, arr2, l2 , mid2 );   
    } 
     
    public static void main(String[] args)   {
     
        int []array1 = {5,25,100};
        int []array2 = {5, 8, 10, 20};
        System.out.println("Items from Array 1: "+Arrays.toString(array1));
        System.out.println("Items from Array 2: "+Arrays.toString(array2));
         
        int med = median(array1, array2);
         
        System.out.println("Median of two arrays: "+ med);
     }
 
 
}

Output

Items from Array 1: [5, 25, 100]
Items from Array 2: [5, 8, 10, 20]
Median of two arrays: 9

Write A Comment