寻找两个正序数组的中位数：思路与实现

一、问题核心知识点
解决该问题需掌握以下关键知识点：
1. 有序数组合并：利用双指针法合并两个有序数组，是处理有序数组的基础操作，时间复杂度O(m+n)。
2. 中位数的计算规则：
若合并后数组长度为奇数，中位数是中间位置的元素；
若为偶数，中位数是中间两个元素的平均值。
3. 二分查找的优化应用：通过二分查找划分两个数组，将时间复杂度优化至O(\log(\min(m,n)))，是本题的核心优化思路。
4. 边界条件处理：划分数组时需考虑数组为空、划分点在数组两端等特殊情况。
二、解法思路与实现
思路1：合并数组法（基础解法）
核心逻辑：
1. 用双指针遍历两个有序数组，按从小到大的顺序合并为一个新数组；
2. 根据新数组的长度奇偶性，计算并返回中位数。

复杂度分析
- 时间复杂度：O(m+n)，需遍历两个数组的所有元素；
- 空间复杂度：O(m+n)，需要额外数组存储合并结果。
思路2：二分查找法（最优解法）
核心逻辑
1. 确保较短的数组作为第一个数组，减少二分查找的次数；
2. 通过二分查找确定第一个数组的划分点，使两个数组的左半部分总元素数为(m+n+1)/2；
3. 保证左半部分的最大值小于等于右半部分的最小值，此时可直接通过划分边界计算中位数。

复杂度分析
- 时间复杂度：O(\log(\min(m,n)))，仅对较短数组进行二分查找；
- 空间复杂度：O(1)，无需额外存储数组，仅使用常量变量。
三、总结
- 合并数组法是解决该问题的基础思路，逻辑简单易懂，适合入门理解，但效率较低；
- 二分查找法是最优解，通过划分数组的思想避免了数组合并，大幅降低了时间复杂度，是面试中需要重点掌握的解法；
- 处理此类有序数组问题时，需重点关注边界条件和二分查找的划分逻辑，这是算法正确性的关键。