LeetCode HOT100 - 寻找两个正序数组的中位数

首先，复杂度要求是 O(log (m+n)) 想到使用二分或者分治之类的解决办法

再考虑题目，找中位数就是去找两个有序数组中的第 k 小元素

只有一个数组的时候是简单的，问题就是在于现在给我们两个数组，且不能先行合并再去做操作

因此不妨从两个数组各自的中位数出发，看看能不能有什么启发

不妨设为数组 a 和 b，a 的中位数是 x ， b 的中位数是 y

若 x <= y ，那我们考虑下能得到什么信息

因为要找的是加起来第 (n + m) / 2 个元素，所以 x 之前的元素肯定不是，y 可能是，但是还要取决于 x 之后的元素情况

但接着呢

如果我们接着是去考虑 a 数组中 > x 且 < y 的元素，和 b 中这样的元素，视图找到一个平衡点恰好使得数量关系实际上就回到了遍历的思路中

我们回想下我们是要二分，二分的核心是每次能排除掉一部分不可能的元素，并进入一个类似结构的子问题，可以用同样的逻辑去处理

这样再和我们前面的形式比对，发现已经有些初步二分的样子了

因为这次比较后，我们排除了一部分元素的可能性（a 数组的前面部分的元素）和剩下的子问题（在两个数组剩下的元素中继续找）

只是进入子问题后我们不能继续找第 (n + m) / 2 个元素了，因为哪些元素相当于被删除了，所以要根据我们删除的元素进行调整

顺着这个思路，我们做些整理和规范化

比如我们之前想的是比较 a 数组中位数和 b 数组中位数，但是进一步做的话这个流程会不容易继续，因为我们要找的是合并数组的第 k 小，而不是两个数组自身的中位数，这个过程中两个数组长度可能不同，而且随着元素不断被排除，目标 k 也在变化，所以每一步的比较点应该跟当前的 k 绑定，而不是固定找各自数组的中位数

所以考虑下面的形式

在两个数组当前还没被排除的部分中，找第 k 小

令 i 指向 nums1 当前起点，j 指向 nums2 当前起点

每次考虑 half = k / 2，去比较 nums1 从 i 开始的第 half 个元素 和 nums2 从 j 开始的第 half 个元素
当然，如果某个数组剩余长度不足 half，就取它的最后一个元素

如果 A[k/2] <= B[k/2]，那么 A 的前 k/2 个数都不可能是第 k 小，