Median of Two Sorted Arrays

You are given two arrays, nums1 of size m and nums2 of size n, each individually sorted in non-decreasing order. Find the median of the m+n numbers obtained by merging the two arrays, without necessarily constructing the merged array. Your algorithm should run in O(log(min(m, n))) time.

Input: The first line contains two integers m and n. The second line contains m space-separated integers (nums1; the line may be empty if m is 0). The third line contains n space-separated integers (nums2; the line may be empty if n is 0). Output: Print the median as a decimal number with exactly one digit after the decimal point.

0 <= m, n <= 1000 m + n >= 1 -10^6 <= nums1[i], nums2[i] <= 10^6

Using +/-infinity SENTINEL values when a partition sits exactly at an array's edge (so there's no real element on one side) is what lets the boundary-comparison logic work uniformly without needing special-case branches for edge partitions.

Find the median of two sorted arrays combined, without necessarily merging them, in better than linear time. Brute force: Fully merge both arrays using a standard two-pointer merge, then directly index into the middle position(s) - this works correctly and runs in O(m+n), which is often acceptable, but doesn't meet the stricter O(log(min(m,n))) requirement this problem explicitly asks for. Optimised: Binary searching on the PARTITION POINT (rather than merging or scanning any actual values) reduces the search to trying different split points on just the SMALLER array, with the larger array's corresponding split fixed by simple arithmetic - each candidate partition is checked with O(1) boundary comparisons, achieving the required O(log(min(m,n))) time.

1. Binary search a PARTITION POINT on the SMALLER array only; the corresponding partition of the LARGER array is then automatically fixed by the requirement that both partitions together hold exactly half of all elements combined. 2. A partition is CORRECT once the largest value on its LEFT side is <= the smallest value on its RIGHT side, checked across BOTH arrays simultaneously; otherwise, shift the smaller array's partition left or right and recompute. 3. Once correct: if the total combined count is odd, the median is the MAX of the two left-side values; if even, it's the AVERAGE of the max of the left sides and the min of the right sides. Use +/-infinity sentinels when a partition sits exactly at an array's edge.

Time: O(log(min(m,n))) - binary search over partition points on the smaller array only. Space: O(1) extra space - no merged array is ever built.

One of the two arrays may be empty (but not both); the total combined count may be even or odd, which changes how the median is computed.

This is widely considered one of the hardest 'medium-labeled' interview problems specifically because of this O(log(min(m,n))) requirement - be ready to carefully explain the partition-validity condition and the median-extraction formula for both the odd and even total-count cases.