34. Median of two sorted arrays of same size

34. Median of two sorted arrays of same size

Problem link :- click here
Approach --->Divide and conquer

package programs;

import java.util.*;

public class Array__34
{

	/*
	    lets create another method to find the median of one array
	    we should take inputs in specific like low and high 
	    because we are going to find the median of specific part of the array by calling recursively
	    
	    Lets find the median of two arrays separately and based on the comparision between the medians 
	    we will remove unnecessary parts and make problem small 
	    m1 -> median of a[]               m2 -> median of b[]
	*/
	static int medianOfTwoSortedArray(int a[], int b[], int low1, int high1, int low2, int high2)
	{
		/*
		    Every recursive function or method should have a basic step
		    if the size of the given array is equal to 2
		    then we can find the minimum of the merged array by 
		    					min( a[o], b[0] )
		    and also find the maximum of the merged array like
		    					max( a[1], b[1] )
		    remaining number of elements is only two which is in the middle
		    			remaining elements are 
		    				max( a[0], b[0] )
		    				 min( a[1],  b[1] )
		    so the median is average of these two elements
		*/
		if(high1 - low1 + 1  == 2 )
		{
			int mid1 = Math.max(a[low1], b[low2]);
			int mid2 = Math.min(a[high1], b[high2]);
			
			return (mid1 + mid2)/2;
		}
		
		int m1 = median(a, low1, high1);
		int m2 = median(b, low2, high2);
		
		int i1 = (high1 + low1)/2;
		int i2 = (high2 + low2)/2;
		
		/*
		CASE1 :-  if(m1==m2)
	    		after merging m1 and m2 will be adjacent 
	    			1) elements in a[] to the LEFT of m1 AND elements in b[] to LEFT of m2
	    				should come to LEFT of m1 and m2 in  merged array as m1 and m2 are adjacent
	    			2) elements in a[] to the RIGHT of m1 AND elements in b[] to RIGHT of m2
	    				should come to RIGHT of m1 and m2 in merged array as m1 and m2 are adjacent
	    		therefore the middle two elements are m1 and m2
	    		so we can return the average of them
		 */
		if(m1 == m2)
			return m1;
		
		/*
		CASE2 :- if(m1<m2)
	    		after merging m1 will be to the LEFT of m2    THEY ARE NOT ADJACENT
	    			1) elements in a[] to the LEFT of m1
	    				should come to        LEFT of m1          (in merged array)
	    			2) elements in b[] to the RIGHT of m2
	    				should come to        RIGHT of m2       (in merged array)
	    		these elements are in the extreme corner so we will leave these elements
	    		and call the same function again but the arrays don't have all the elements 
	    		low1 --->  index of middle                        high1  --->   same
	    		low2 ---> same                                          high2 --->    index of middle 
		 */
		else if(m1 < m2)
			return medianOfTwoSortedArray(a, b, i1, high1, low2, i2);
		//similarly
		else
			return medianOfTwoSortedArray(a, b, low1, i1, i2, high2);
	}
	
	static int median(int arr[], int low, int high)
	{
		int n = (high - low)+1;
		
		int median = 0;
		
		if(n%2==1)
		{
			int mid = (low + high)/2;
			median = arr[mid];
		}
		else if(n%2==0)
		{
			int mid1 = (low+high)/2;
			int mid2 = mid1 + 1;
			median = (arr[mid1] + arr[mid2])/2;
		}
		
		return median;
	}
	
	public static void main(String[] args)
	{
		int i, n, ans;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the arrays : ");
		n= s.nextInt();
		int array1[] = new int[n];
		int array2[] = new int[n];
		System.out.println("Enter the elements of the array 1 : ");
		for(i=0; i<n; i++)
			array1[i] = s.nextInt();
		System.out.println("Enter the elements of the array 2 : ");
		for(i=0; i<n; i++)
			array2[i] = s.nextInt();
		
		System.out.println("Array 1 : ");
		printArray(array1);
		System.out.println("\nArray 2 : ");
		printArray(array2);
		
		ans = medianOfTwoSortedArray(array1, array2, 0, n-1, 0, n-1);
		System.out.println("\n\nMedian is : " + ans);
	}

	static void printArray(int arr[])
	{
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O( log(n) )
Space complexity :- O(1)