mq011.寻找两个正序数组的中位数

题目链接

啊我看到题的第一反应就是使用归并的方式（参考lc088），可是归并的方式时间复杂度为O（M+N），不满足题意的O(log(M+N))，注意到时间复杂度里有log存在，我们可以考虑用二分查找法。在这之前，我们讲一下暴力求解法，即先将两个数组合并然后用排序算法排序后取出中位数，这种算法的时间复杂度一般为O((M+N)log(M+N))，这个时间复杂度过大，是因为其没有利用原先两个数组是有序的这一特性。

现在考虑二分查找法，首先，我们考虑只有一个有序数组的情况，我们可以用一条线将数组划分成两部分，在数组元素总数为偶数的情况下，线的两侧分别为求中位数要用到的两个数字，在数组元素总数为奇数的情况下，线可以划分在中间偏右侧的位置，也就是左半部分刚好比右半部分多一个元素并且这个靠近线的左侧的元素就是中位数。当拓展到两个有序数组的时候我们也可以用线同时划分两个数组，划分完后，除了两侧的元素个数满足一定条件之外（关于两个数组中元素个数的和），还能满足线左侧所有元素的数值全都小于等于线右边的所有元素的数值。这样，那么中位数就一定只与线两侧的元素有关，确定这条线的位置用二分查找

这个算法的时间复杂度是O（N），空间复杂度是O（N）。