$$题意$$

题目绕的有一点远，其实原意特别简单：

已知两个升序序列，求这两个序列合并后的中位数。

知道了题目啥意思，我们再来考虑解法。

$$解法$$

1 快速排序

我们可以建立一个数组存住两个序列的所有元素，接着对这个数组进行排序，最后返回的就是这个数组的中位数。

时间复杂度 $O(NlogN)$，$10^5$ 不是问题。

2 数据结构维护

这题需要的数据结构是维护序列中间一个元素的，不多唠嗑，因为也不是我知道的最优解。

一般的数据结构时间复杂度是 $O(NlogN)$（怨我无能，我只想到了 优先队列、平衡树、对顶堆，有别的想法的朋友可以评论提出 qaq），依旧可以过掉。

3 双指针算法

不用说太多，一提名字大家应该都想到了：我们可以建立两个指针分别指向两个序列的第一个元素，并建立一个变量 $d$ 表示现在已经找过了多少个元素，因为从第一个元素搜起，所以它的初值为 2，时间复杂度为 $O(N)$

这时，若 $d$ 到了中位数的位置，那么我们就可以输出两个位置的最大值（因为 $d$ 包括现在搜到的两个元素），否则，我们进行分类讨论：

1. 若序列 1 的下一元素大于序列 2 的元素
   我们就让序列 2 的指针跳到下一个
2. 反之，我们就让序列 1 的指针跳到下一个

为什么要这样？很简单，就维护序列的单调性。

有同学要问了，确定不需要特判一个序列的指针在搜索到中位数前，到达了尾指针的可能？

其实不需要，设序列的长度为 $x$（两序列等长），则中位数为 $x \times 2 \div 2 = x$，即中位数的位置不会超过序列长度。

但是还有一个情况要特判的（不知道有没有这个数据，因为我没试过 qaq），就是当序列长度为 $1$ 的时候，这个方法就不管用了，这时候我们就要返回 $min (S1_0, S2_0)$ ，因为我们的假想序列初始为 $2$；当然如果您初始序列长度为 $0$ 我也无话可说。

Code：

class Solution {
public:
    int medianSearch(vector<int>& S1 , vector<int>& S2) {
        auto it1 = S1.begin(), it2 = S2.begin(); // 迭代器模拟
        if (S1.size() == 1) return min (*it1, *it2); // 特判
        int d = 2;
        while (it1 != S1.end() && it2 != S2.end()) {
            if (d == S1.size()) return max (*it1, *it2); // 先判断后放数
            auto It1 = it1 + 1, It2 = it2 + 1;
            if (*It1 > *It2) ++ it2;
            else ++ it1;
            ++ d; // 记得序列 + 1，不然就 boom 了
        }
    }
};

大家有建议的可以下面评论区提出，有价值的建议免费赠送一个不值钱的关注（