acqcc

4. Median of Two Sorted Arrays

Jun 24, 20223 min read

Problem Statement

Pattern: Binary Search

Solution

public double findMedianSortedArrays(int[] a, int[] b) {
	int n1 = a.length, n2 = b.length, total = n1 + n2, half = total / 2;
	if (n1 > n2) return findMedianSortedArrays(b, a);   // let a -> shorter array
	
	int start = -1, end = n1;
	while (true) {
		// a partition's ptr
		int mid = start + (end-start)/ 2;
		// b partition's ptr -> determined a-pointer 'mid'
		int bmid = half - mid - 2;   // -2 to offset 0-based error
		
		// a and b partition's left and right values, accounting for Out Of Bounds
		int aleft = (mid >= 0) ? a[mid] : Integer.MIN_VALUE;
		int aright = (mid + 1 < n1) ? a[mid + 1] : Integer.MAX_VALUE;
		int bleft = (bmid >= 0) ? b[bmid] : Integer.MIN_VALUE;
		int bright = (bmid + 1 < n2) ? b[bmid + 1] : Integer.MAX_VALUE;
		
		// aleft partition is overextending
		if (aleft > bright) end = mid - 1;
		// bleft partition is overextending
		else if (bleft > aright) start = mid + 1;
		// both partitions are perfect -> return median
		else {   // aleft <= bright && bleft <= aright
			// odd
			if (total % 2 != 0) return Math.min(aright, bright);
			// even
			else return (double) (Math.max(aleft, bleft) + Math.min(aright, bright)) / 2;
		}
	}
}

Notes

Explanation:

Median of Two Sorted Arrays - Binary Search - Leetcode 4 - YouTube

  • First take a glance at the approach we took towards the problem GFG Median of 2 Sorted Arrays of Same Size
  • In this case, instead of n the position where we will find the median is (n1+n2)/2, which here we take to be half = total / 2
  • start and end are unintuitively intialised to int start = -1, end = n1 to address an edge case, where a is of length 1, and aleft > bright (check Notes)
  • now with that out of the way
  • the final ‘merged’ array will have some elements from the ‘smaller’ array and some from the other one.
  • when we pick let’s say x elements from a, we are forced to pick half - x elemebts from b. Since a and b are the only 2 arrays to be merged
  • This question can be rephrased as PICK THE SMALLEST ‘M+N/2’ ELEMENTS FROM 2 SORTED ARRAYS.
  • so we apply binary search to find that sweet spot x in a.
  • just watch the video

Graph

Backlinks