The Kth Element: Median of Two Sorted Arrays

In the Hall of Records, the Royal Statistician must find the median of two sorted arrays without merging them. The arrays may have different sizes, and the Statistician needs O(log(min(m,n))) time complexity. "Binary search on the smaller array," the Statistician says. "Partition both arrays so that the left half contains exactly half the elements, all smaller than the right half. The median is at the boundary." Given two sorted arrays of sizes m and n, find the median of the combined sorted array. If m+n is odd, the median is the middle element. If m+n is even, the median is the average of the two middle elements. Output the median as a decimal with one decimal place. Constraints: 0 <= m, n <= 10^5, arrays are sorted, m+n >= 1 Input: 2 1 3 1 2 Output: 2.0 Input: 2 1 2 2 3 4 Output: 2.5