题目链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/description/
我的思路
这是一道困难级别的题，确实非常难，在时间复杂度的限制下，只能采用二分法来进行求解，关键是如何进行二分。自己拿到这题完全没有思路。
题解
官方题解给了两种办法，一种是直接双指针搜索，判断规则非常复杂，程序也很长，尽管时间复杂度表现很优秀，但还是有点难理解，这里复述另一种解法，切分的思路，因为我们要找的是中位数，统计中，中位数的作用是：
将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。
假设两个序列的长度分别为m和n，那么于是乎，我们可以尝试划分两个序列，就会每个序列各自得到两个子集，将两个序列前部分子集合并、后部分子集合并，再判断当前切分得是否合理，如果合理，找到前一个合并子集的最大值、后一个合并子集的最小值，返回平均值（当m + n为偶数时），或直接返回前一个合并子集的最大值（当m + n为奇数时）。这样的思路里有两个地方需要进一步讨论：1. 如何划分子集？ 2. 如何判断划分得是否合理？接下来逐步讨论这两个问题：
如何划分子集
令两个序列分别为A, B，那么假设我们在序列A的i索引处切一刀，B的j索引处切一刀，那么我们就可以得到下面的切分：
$A[0]\cdots A[i-1]\ |\ A[i]\cdots A[m-1]$
$B[0]\cdots B[j-1]\ |\ B[j]\cdots B[m-1]$
A中有m个元素，所以一共有m + 1种切分办法，对应地B能有n + 1种切分办法
我们把$A[0]\cdots A[i-1]$和$B[0]\cdots B[i-1]$放到一起，称为left_part，剩下的$A[i]\cdots A[m-1]$和$B[j]\cdots B[n-1]$放到一起，称为right_part
如何判断切分得合理
根据统计中中位数的定义，如果我们的划分合理，那么应该满足：
$\max(left\_part)\leq \min(right\_part)$
$len(left\_part)=len(right\_part)\ or \ len(right\_part)+1$
其中第一条是无论m + n是奇数还是偶数都共同满足的，第二条要分情况，当m + n为偶数时，则取前一个条件，反之取后一个条件，只有这样，才是“恰好”切分，长度上符合要求，数值上也符合要求（不然比如[1,2,3,4|10]和[1,2|9,11]，这样也能满足第一条条件，但并不是最佳的切分，因此还要加上第二条条件）
现在我们已经归纳出了两个必要的条件，那么代码实际操作起来该怎么写呢？代码离不开数学表示，有了文字的概念表述，还需要将这些表述进一步转化为数学表达式，才能清晰地在代码中体现和实现算法。根据上面的描述，我们可以得出：
$i+j=m-i+n-j$ 或 $i+j=m-i+n-j+1$
上述两式分别对应m + n为偶数和奇数时，也就是上面第二点中的第二个条件，对这个式子进行简化，把i + j全部移到一边，可以得到：
$i+j=\lfloor\frac{m+n+1}{2}\rfloor$
通过向下取整操作，可以将两个式子用上式直观地表达出来，无论m + n是奇数还是偶数，直接代入计算即可。为不失一般性，我们先假设m ≤ n，也就是A的长度小于等于B的长度，于是乎i的取值范围满足$0≤i≤m$（为什么是到m，因为根据第1点的讨论，对于m长的序列而言，有m + 1种划分方法，这里我们不再是二分索引位置，因此范围不是从0到m - 1），那么我们只需要在这个范围内枚举i，即可求得$j=\lfloor\frac{m+n+1}2\rfloor-i$，不需要再加入额外的判断条件了。这种情况下，如果A的长度更长，则只需要交换A和B就行了。
但是这种情况下（也是二分法中常见到的特殊情况，就是边界值），i和j有可能触碰到边界值m和n或0，直接获取A[m]会out of index，或A[i-1]即A[-1]会取错值，不符合我们的算法要求，因此需要对这几种情况来进行处理。实际上i和j只代表了划分点的位置，但是在程序里我们要依靠i和j的实际值来取出序列种对应位置的元素值进行判断，比如假设i = 0，那么A的划分点为0，此时A[-1]是不存在的，因为整个序列A都被划进了right_part里，但是根据我们上面的假设，我们又要取A[-1]来作为我们判断left_part里最大值的依据，就会出现错误。处理这种情况的办法其实也很简单，只需要规定：$A[-1]=B[-1]=-\infty, A[m]=B[n]=\infty$即可，理解起来也很简单：
当一个数组不出现在前一部分时，对应的值为负无穷，就不会对前一部分的最大值产生影响；当一个数组不出现在后一部分时，对应的值为正无穷，就不会对后一部分的最小值产生影响。
于是乎，上面的整个讨论过程可以抽象为：
在$[0,m]$中找到最大的i，使得$A[i-1]\leq B[j]$，其中$j=\lfloor\frac{m+n+1}2\rfloor-i$
那么我们就可以在[0,m]中对i进行二分搜索，找到最大的满足以上条件的i值即可。回顾一下我们的切分思路：
$A[0]\cdots A[i-1]\ |\ A[i]\cdots A[m-1]$
$B[0]\cdots B[j-1]\ |\ B[j]\cdots B[m-1]$
关键的值就在于i - 1, i, j - 1, j这几个位置，这里我们定义几个中间变量来便于比较：
- nums_i1 = (-inf if i == 0 else nums1[i - 1])
- nums_i = (inf if i == m else nums1[i])
- nums_j1 = (-inf if j == 0 else nums2[j - 1])
- nums_j = (inf if j == n else nums2[j])
关键在于比较A[i-1]和B[j]的值，如果满足$A[i-1]\leq B[j]$，那就先赋值一个left_part的最大值median1 = max(nums1[i-1], nums2[j-1]，以及right_part的最小值median2 = min(nums1[i], nums2[j])，这两个中间值用于返回最后的中位数，然后再把搜索区间从左缩小，l = i + 1，看一看i的后面是否还有满足条件的取值，不断缩小区间；如果$A[i-1]>B[j]$，那就说明此时i掠过了我们要找的值，i太靠右了，要从右边缩短区间，r = i - 1，重复以上过程，直到l > r时溢出，返回我们的最终值，如果(m + n) % 2 == 0，说明总长度为偶数，返回两个median值的平方，如果总长度为奇数则返回median1，因为根据我们的算法设计，median1始终是在总长为奇数情况下更长的那一个
反思
- 明确二分的对象，是要二分角标、位置，还是要二分元素，充分理解要二分的变量在实际问题中的含义，比如这里的二分变量为i，i对应了切分点的位置，而切分点有m + 1种可能，所以i的取值范围是$[0,m]$，而不是往常的m - 1
- 为什么left_part在总序列长度为奇数时一定是更长的那一个，以至于我们可以直接在此情况下返回median1？根据我们的题解思路，left_part的总长度为$i+j=\frac{m+n+1}{2}$，一定是大于右边的长度$m-i+n-j$的（因为$\frac{m+n+1}{2}-m+i-n+j=\frac{m+n+1}{2}-m-n+\frac{m+n+1}{2}=m+n+1-m-n=1>0$，所以len(left_part)在此情况下始终>len(right_part)，且一定会长出1个元素来，这个元素就是我们要的答案）
二分法一定能收敛到我们想要的那个值，因为
i的区间是[0, m]，有限个切分点- 每次二分都排除了不满足的部分
- 至少有一个合法切分存在（因为数组整体有序，左半部分的总数固定是
(m+n+1)//2，必然能切出来）
- 用数学归纳法来对问题进行抽象，用数学公式来直接表示问题，用好数学工具
结果
0ms 100%, 17.78% 57.53%
