两个有序数组的中位数

Median of Two Sorted Arrays

问题：两个有序数组的中位数

考察：数组、二分查找

来源：Citadel

链接：https://www.jointaro.com/interviews/questions/median-of-two-sorted-arrays/

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

解析

思路：在较短数组上二分切分位置，使左右两边元素数量相等且左半最大值不大于右半最小值。找到合法切分后按总长度奇偶返回中位数。

复杂度：时间 O(log min(m,n))，空间 O(1)。