35. Median of Two Sorted Arrays

Given two sorted arrays (of possibly different sizes), find the median of all elements combined. Print the median rounded to exactly one decimal place.

Input: The first line contains n1 followed by a line with n1 space-separated sorted integers (array 1). The next line contains n2 followed by a line with n2 space-separated sorted integers (array 2). Output: Print the median of the two combined arrays, rounded to exactly one decimal place.

1 <= n1, n2 <= 10^5

For an EVEN combined length, the median is the average of the two true middle elements - for an ODD combined length, it's just the single true middle element; getting this parity check right is the most common source of off-by-one bugs here.

Given two already-sorted arrays (possibly of different sizes), find the median value as if they were merged into one single sorted array. Brute force: Merge both arrays fully into one new sorted array (a simple two-pointer merge) and directly index into the middle - this is simple, correct, and runs in O(n1 + n2), which is efficient enough for most practical constraints. Optimised: For truly huge arrays, a more advanced binary-search-based partitioning approach finds the median in O(log(min(n1,n2))) by directly searching for the correct 'split point' in the smaller array without ever merging anything - but a straightforward merge-based approach is simpler to implement correctly and entirely acceptable unless asked specifically to optimize further.

You don't actually need the fully merged array - only its middle element(s). Walk two pointers through the two arrays simultaneously, always advancing the pointer with the smaller current value (as in a merge), but instead of storing every merged value, just keep track of the last one or two values produced once you reach the middle position(s) of the combined length. This produces the same answer as fully merging, but without ever allocating an output array, so space drops to constant while time stays linear. Time: O(n1 + n2) Space: O(1)

Merge the two sorted arrays into a single sorted array of size n1+n2, the same way the merge step of merge sort works: repeatedly compare the fronts of both arrays and take the smaller one. Once merged, the median is read directly off the middle element (or the average of the two middle elements if the total length is even). This is simple and clearly correct, but it uses extra space proportional to the combined array size, which isn't necessary just to find one value. Time: O(n1 + n2) Space: O(n1 + n2)

Binary search on the smaller array to choose a partition point that splits both arrays combined into a left half and a right half of equal (or near-equal) size, such that every element in the left half is <= every element in the right half. This is checked cheaply by comparing the boundary elements around the candidate partitions in both arrays; if the condition fails, binary search adjusts the partition point up or down. Once the correct partition is found, the median is computed directly from the boundary elements, without ever touching most of the elements in either array - this is the fastest known approach, working in logarithmic time relative to the smaller array. Time: O(log(min(n1, n2))) Space: O(1)

1. Conceptually merge both sorted arrays together (using a two-pointer merge, without necessarily storing the whole merged result). 2. Track just enough of the merge process to identify the middle element(s) - the combined length tells you whether you need one middle value (odd total) or the average of two middle values (even total). 3. Print that median rounded to exactly one decimal place.

Time: O(n1 + n2) for the merge-based approach - a single combined linear pass; O(log(min(n1,n2))) for the advanced binary-search partition approach. Space: O(n1 + n2) if fully merging, or O(1) if only tracking the merge position needed to identify the median without storing the whole result.

n1 = n2 = 1 (two single-element arrays, as in the example); a combined length that is even (median averages two middle values) versus odd (a single middle value); and n1 or n2 at the largest size 10^5 (confirming the approach avoids a slow full merge).

This is one of the most famous 'hard' array interview questions specifically BECAUSE of the O(log(min(n1,n2))) binary-search solution - be ready to at least describe the merge-based approach clearly, and mention the harder binary-search partition method exists as the theoretically optimal follow-up.