CC-17 : Find Median of 2 arrays.

Description:

Given two sorted input arrays as input, find the median of the combined numbers of the 2 arrays.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array1: 3, 22, 44, 67, 77, 88, Array2: 96, 122, 144, 201, 220,	Median of the 2 arrays is 88
Array3: 3, 22, 44, 67, 77, 88, Array4: 90, 96, 122, 144, 201, 220,	Median of the 2 arrays is 89

Pseudocode:

searchInSortedMatrix(nums[][], toSearch):

Return -1.

Integer array named nums1 and nums2 are received as input parameters.

Set integer variable n1len to nums1.length.

Set integer variable n2len to nums2.length.

If (n1len > n2len) ,call medianOf2Arrays(nums2, nums1).

Set integer variable totalLen to (n1len +n2Len).

Set integer variable left to (n1Len+n2Len+1)/2.

Set integer variable firstIdx to zero, we will use this variable to check the first index of partition in which are searching for required integer.

Set integer variable lastIdx to nums1.length-1, we will use this variable to check the last index of partition in which are searching for required integer.

While (firstIdx <= lastIdx) do the following steps:

Set integer variable mid1 to (lastIdx+firstIdx)/2.

Set integer variable mid2 to (left-mid1).

Initialize variables l1, l2, r2,r2.

If mid1 > 0 set l1=nums1[mid1-1] else set l1 to Integer.MinValue.

If mid2 > 0 set l2=nums1[mid2-1] else set l1 to Integer.MinValue.

If mid1 < n1Len set r1=nums1[mid1] else set r1 to Integer.MaxValue.

If mid2 < n2Len set r2=nums2[mid2] else set r2 to Integer.MaxValue.

If l1<=r2 and l2 <=r1:

if totallen%2=1, then if l1>l2, return l1 else return l2.

Else:

Initialize variables med1 and med2.

If (l1>l2) then med1=l1 else med1=l2.

If r1 < r2 then med2=r1 else med2=r2.

Return (med1+med2)/2.

o Else if (l1 > r2) then firstIdx=mid1-1.

Else:

Set firstIdx=mid1+1.

Code:

public int medianOf2Arrays(int[] nums1, int[] nums2){
	int n1Len=nums1.length;
	int n2Len=nums2.length;
	if (n1Len > n2Len) {return medianOf2Arrays(nums2, nums1);}
	int totalLen=n1Len+n2Len;
	int left=(n1Len+n2Len+1)/2;
	int firstIdx=0;
	int lastIdx=nums1.length;
	while (firstIdx <= lastIdx) {
		int mid1=(lastIdx+firstIdx)/2;
		int mid2=left-mid1;
		int l1,l2,r1,r2;
		if (mid1 > 0) {
			l1= nums1[mid1-1];
		} else {  
			l1=Integer.MIN_VALUE;
		}	
		if (mid2 > 0) {
			l2= nums2[mid2-1];
		} else {  
			l2=Integer.MIN_VALUE;
		}	
		if (mid1 < n1Len) {
			r1= nums1[mid1];
		} else {  
			r1=Integer.MAX_VALUE;
		}
		if (mid2 < n2Len) {
			r2= nums2[mid2];
		} else {  
			r2=Integer.MAX_VALUE;
		}	
		if ((l1 <= r2) && (l2 <=r1)) {
			if (totalLen % 2==1) {
				if (l1> l2) {
					return l1;
				}else {
					return l2;
				}				
			}else {
				int med1; int med2;
				if (l1> l2) {
					med1=l1;
				}else {
					med1=l2;
				}	
				if (r1< r2) {
					med2=r1;
				}else {
					med2=r2;
				}
				return (med1+med2)/2;
			}
		} else if (l1 > r2) {
			lastIdx=mid1-1;
		}else {
			firstIdx=mid1+1;
		}		
	}	
	return -1;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SearchMedianOf2Arrays {

public int medianOf2Arrays(int[] nums1, int[] nums2){
	int n1Len=nums1.length;
	int n2Len=nums2.length;
	if (n1Len > n2Len) {return medianOf2Arrays(nums2, nums1);}
	int totalLen=n1Len+n2Len;
	int left=(n1Len+n2Len+1)/2;
	int firstIdx=0;
	int lastIdx=nums1.length;
	while (firstIdx <= lastIdx) {
		int mid1=(lastIdx+firstIdx)/2;
		int mid2=left-mid1;
		int l1,l2,r1,r2;
		if (mid1 > 0) {
			l1= nums1[mid1-1];
		} else {  
			l1=Integer.MIN_VALUE;
		}	
		if (mid2 > 0) {
			l2= nums2[mid2-1];
		} else {  
			l2=Integer.MIN_VALUE;
		}	
		if (mid1 < n1Len) {
			r1= nums1[mid1];
		} else {  
			r1=Integer.MAX_VALUE;
		}
		if (mid2 < n2Len) {
			r2= nums2[mid2];
		} else {  
			r2=Integer.MAX_VALUE;
		}	
		if ((l1 <= r2) && (l2 <=r1)) {
			if (totalLen % 2==1) {
				if (l1> l2) {
					return l1;
				}else {
					return l2;
				}				
			}else {
				int med1; int med2;
				if (l1> l2) {
					med1=l1;
				}else {
					med1=l2;
				}	
				if (r1< r2) {
					med2=r1;
				}else {
					med2=r2;
				}
				return (med1+med2)/2;
			}
		} else if (l1 > r2) {
			lastIdx=mid1-1;
		}else {
			firstIdx=mid1+1;
		}		
	}	
	return -1;
}

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	
	SearchMedianOf2Arrays search=new SearchMedianOf2Arrays();
	int[] nums1= {3,22,44,67,77, 88};
	int[] nums2= {96,122,144,201,220};
	System.out.println("\nArray1:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums1.length; arrayIndex++) {
		System.out.print(nums1[arrayIndex]+", ");		
	} 
	System.out.println("\nArray2:");
	arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums2.length; arrayIndex++) {
		System.out.print(nums2[arrayIndex]+", ");		
	} 
	retVal=search.medianOf2Arrays(nums1, nums2);
		
	System.out.println("\n\nMedian of the 2 arrays is "+ retVal);	
	
	int[] nums3= {3,22,44,67,77, 88};
	int[] nums4= {90,96,122,144,201,220};
	System.out.println("\nArray3:");
	arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums3.length; arrayIndex++) {
		System.out.print(nums3[arrayIndex]+", ");		
	} 
	System.out.println("\nArray4:");
	arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums4.length; arrayIndex++) {
		System.out.print(nums4[arrayIndex]+", ");		
	} 
	retVal=search.medianOf2Arrays(nums3, nums4);
		
	System.out.println("\n\nMedian of the 2 arrays is "+ retVal);	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

}