求两个有序数组的中位数或者第k小元素

给定两个有序数组，假设数组 `nums1` 的长度为 `m`，数组 `nums2` 的长度为 `n`。为了方便起见，假设 `m ≤ n`。要求解这两个有序数组的中位数或第 `k` 小的元素，可以采用以下两种方法。

## 方法一：归并排序

这种方法的思路很简单，就是将两个有序数组归并成一个有序数组，然后再根据数组长度和 k 的值确定中位数或第 k 小的元素。具体步骤如下：

1. 定义两个指针 `p1` 和 `p2`，分别指向数组 `nums1` 和 `nums2` 的起始位置。
2. 定义一个新数组 `nums3`，用于存放归并后的有序数组。
3. 循环执行以下步骤，直到 `nums3` 中有 `k` 个元素：
1. 比较 `nums1[p1]` 和 `nums2[p2]` 的大小，将较小的元素加入 `nums3` 中。
2. 将指向较小元素的指针后移一位。
4. 如果 `m + n` 是奇数，则 `nums3[(m+n)/2]` 就是中位数；否则 `nums3[(m+n)/2-1]` 和 `nums3[(m+n)/2]` 的平均值就是中位数。如果要求第 k 小的元素，则返回 `nums3[k-1]`。

时间复杂度为 $O(m+n)$。

## 方法二：二分查找

这种方法的思路比较巧妙，其核心思想是在两个有序数组中找到第 k 小的元素，假设这个元素在数组 `nums1` 的位置是 `i`，在数组 `nums2` 的位置是 `j`。那么有以下两种情况：

1. 如果 `nums1[i] < nums2[j]`，则数组 `nums1[0...i]` 中的所有元素都是第 k 小的元素的候选元素，因为这些元素都小于 `nums2[j]`，而 `nums2[0...j]` 中的所有元素都不可能是第 k 小的元素，因为这些元素都小于 `nums1[i]`。
2. 如果 `nums1[i] >= nums2[j]`，则数组 `nums2[0...j]` 中的所有元素都是第 k 小的元素的候选元素，因为这些元素都小于 `nums1[i]`，而 `nums1[0...i]` 中的所有元素都不可能是第 k 小的元素，因为这些元素都小于 `nums2[j]`。

具体步骤如下：

1. 定义两个指针 `p1` 和 `p2`，分别指向数组 `nums1` 和 `nums2` 的起始位置。
2. 循环执行以下步骤，直到找到第 k 小的元素：
1. 如果 `p1 >= m`，说明数组 `nums1` 已经没有元素可以参与比较，直接返回 `nums2[p2+k-1]`。
2. 如果 `p2 >= n`，说明数组 `nums2` 已经没有元素可以参与比较，直接返回 `nums1[p1+k-1]`。
3. 如果 `k == 1`，直接返回 `min(nums1[p1], nums2[p2])`。
4. 比较 `nums1[p1+k/2-1]` 和 `nums2[p2+k/2-1]` 的大小，如果前者小于等于后者，则说明 `nums1[0...k/2-1]` 中的所有元素都小于等于第 k 小的元素，可以把这些元素全部排除掉，更新 `k` 的值为原来的一半，并将指向 `nums1` 的指针后移 `k/2` 个位置；否则说明 `nums2[0...k/2-1]` 中的所有元素都小于等于第 k 小的元素，可以把这些元素全部排除掉，更新 `k` 的值为原来的一半，并将指向 `nums2` 的指针后移 `k/2` 个位置。
3. 如果要求中位数，则返回第 `(m+n)/2` 小的元素和第 `(m+n)/2+1` 小的元素的平均值；如果要求第 k 小的元素，则返回第 k 小的元素。

时间复杂度为 $O(\log(m+n))$。