Leetcode 4. 测试和训练两个有序数组的中位数

心路历程解析

这道题目如果采用暴力解法，实现起来较为简单。然而，一旦看到题目要求复杂度必须达到 O(log(m+n))，那么唯一可行的方案只能是使用双指针法。不过在实际测试过程中发现，采用归并排序的方式反而运行得更快。这或许正是平均复杂度与实际运行效率之间存在差异的原因所在。

关于二分法的实现思路如下：

为了寻找第 k（k>1）小的元素，首先需要选取两个基准值 pivot1 = nums1[k/2-1] 与 pivot2 = nums2[k/2-1] 并进行比较。若 pivot1 与 pivot2 相等，则可以确定 nums1 数组中从起始位置到 k/2-1 的所有元素都不可能是第 k 小的元素。将这些元素排除后，剩余部分可作为新的 nums1 数组继续处理。同样的逻辑也适用于 pivot2 的情况。

在一般情况下，nums1 中小于等于 pivot1 的元素数量为 k/2-1 个，而 nums2 中小于等于 pivot2 的元素数量也为 k/2-1 个。此时取较小的那个基准值作为当前的 pivot，并统计两个数组中小于等于该值的总数量。这个总数量不会超过