35. Median of two sorted arrays of different sizes

35. Median of two sorted arrays of different sizes

Problem link :- click here
Approach ---> Binary search

package programs;

import java.util.*;

public class Array__35
{

	/*
	    we know how to find the median if we are given 2 arrays of size 2
	    we will use that here 
	    1) we will cut both the arrays in such a way that the left parts of both 
	        the arrays together form the left half of the merged array
	                              l1   r1
	        		a[] = {  1,  4,  8,  10,  11  }
	        		b[] = {  2,  5,  6,  9  }
	        		            l2   r2
	               l1 ->  last element of   a[] to the left of the median in the merged array
	               l2 ->  last                     b[]            left           median
	               r1 ->  first                    a[]           right         median
	               r2 ->  first                   b[]           right         median
	               
	    2) we should cut, in such a way that the below condition should obey
	    			l1     <    r2
	    			l2    <     r1
	          there other conditions like   l1 < r1    and     l2 < r2  
	          since the given arrays are sorted we need not check these elements
	                           NOTE :- we are not cutting the arrays in the first attempt 
	          in the first cycle we take 'n1/2' elements from a[]
	          					and the remaining from  b[]
	          we will use BINARY SEARCH to find the position effectively
	          
	    3) As mentioned above we are reducing the 2 arrays of size n1 and n2 
	         to two arrays both of size 2    i.e.,
	          			l1      r1
	          			l2     r2
	         a) if the sum of the sizes of the arrays is even then median is the average of two middle elements
	         	 l1,  l2      are the left    part
	         	 r1,  r2      are the right part
	              so the average should be between    
	               							max( l1, l2 )  and   min( r1, r2 )
	         b) if the sum of the sizes of the arrays is odd then median is  a SINGLE element
	         	 since we take only (n1 + n2)/2.  when (n1 + n2) is odd median will be in the right part
	         	 	 so the median is 
	         	 	 				min( r1, r2 )
	*/
	
	static int medianOfTwoSortedArraysOfDifferentSize(int a[], int b[], int n1, int n2)
	{
		int low, high;
		low = 0;
		high = n1;
		
		while(low<=high)
		{
			//cut1 --->  number of elements from a[]     to left of the merged array
			//cut2 --->  remaining number of elements to left of the merged array from b[]
			int cut1 = (low + high)/2;
			int cut2 = (n1+n2)/2 - cut1;
			
			//after cutting lets store the values in to the variables
			int left1 = (cut1==0)  ? Integer.MIN_VALUE : a[cut1-1];
			int left2 = (cut2==0) ? Integer.MIN_VALUE : b[cut2-1];
			
			int right1 = (cut1==n1)   ? Integer.MAX_VALUE : a[cut1];
			int right2 = (cut2==n2) ? Integer.MAX_VALUE : b[cut2];
			
			//3 point
			if(  left1 <= right2    &&    left2 <= right1  )
			{
				if(    (n1+n2)%2 == 0   )
					return (    Math.max(left1, left2)   +   Math.min(right1, right2)    )  /2  ;
				else
					return Math.min(right1, right2);
			}
			else if(left1 > right2)
				high  = cut1 - 1;
			else
				low = cut1 + 1;
		}
		
		return -1;
	}
	
	public static void main(String[] args)
	{
		int i, n1, n2, ans;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array 1 : ");
		n1 = s.nextInt();
		int array1[] = new int[n1];
		System.out.println("Enter the elements of the array 1 :");
		for(i=0; i<n1; i++)
			array1[i] = s.nextInt();
		System.out.print("Enter the size of the array 2 : ");
		n2 = s.nextInt();
		int array2[] = new int[n2];
		System.out.println("Enter the elements of the array 2 : ");
		for(i=0; i<n2; i++)
			array2[i] = s.nextInt();
		
		System.out.println("Array 1 : ");
		printArray(array1);
		System.out.println("\nArray 2 : ");
		printArray(array2);
		
		ans = medianOfTwoSortedArraysOfDifferentSize(array1, array2, n1, n2);
		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( min(log₂n1 , log₂n2) )
Space complexity :- O(1)