两个排序数组的中值（两个排序数组的中位数）
两个排序数组的中值（两个排序数组的中位数）由于 A 中有 m 个元素， 所以我们有 m 1 种划分的方法（i = 0 ∼ m）。首先，让我们在任一位置 i 将 A 划分成两个部分：为了解决这个问题，我们需要理解 “中位数的作用是什么”。在统计中，中位数被用来：将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。如果理解了中位数的划分作用，我们就很接近答案了。
题目描述：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m n)) 。
示例 1:
示例 2:
为了解决这个问题，我们需要理解 “中位数的作用是什么”。在统计中，中位数被用来：
将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。
如果理解了中位数的划分作用，我们就很接近答案了。
首先，让我们在任一位置 i 将 A 划分成两个部分：
由于 A 中有 m 个元素， 所以我们有 m 1 种划分的方法（i = 0 ∼ m）。
我们知道：
len(left_A) = i，len(right_A) = m − i
注意：当 i = 0 时，left_A 为空集， 而当 i = m 时，right_A 为空集。
采用同样的方式，我们在任一位置 j 将 B 划分成两个部分：
将 left_A 和 left_B 放入一个集合，并将 right_A 和 right_B 放入另一个集合。 再把这两个新的集合分别命名为 left_part 和 right_part：
如果我们可以确认：
1. len(left_part) = len(right_part)
2. max(left_part) ≤ min(right_part)
那么，我们已经将 {A B} 中的所有元素划分为相同长度的两个部分，且其中一部分中的元素总是大于另一部分中的元素。那么：
要确保这两个条件，我们只需要保证：
ps.1 为了简化分析，我假设 A[i−1]，B[j−1]，A[i]，B[j] 总是存在，哪怕出现 i = 0，i = m，j = 0，或是 j = n 这样的临界条件。 我将在最后讨论如何处理这些临界值。
ps.2 为什么 n ≥ m？由于 0 ≤ i ≤ m 且 j = (m n 1) / 2 - i，我必须确保 j 不是负数。如果 n < m，那么 j 将可能是负数，而这会造成错误的答案。
所以，我们需要做的是：
当找到目标对象 i 时，中位数为：
现在，让我们来考虑这些临界值 i=0，i=m，j=0，j=n，此时 A[i−1]，B[j−1]，A[i]，B[j] 可能不存在。 其实这种情况比你想象的要容易得多。
我们需要做的是确保 max(left_part) ≤ min(right_part)。 因此，如果 I 和 j 不是临界值（这意味着 A[i−1]，B[j−1]，A[i]，B[j] 全部存在） 那么我们必须同时检查 B[j−1] ≤ A[i] 以及 A[i−1] ≤ B[j] 是否成立。 但是如果 A[i−1]，B[j−1]，A[i]，B[j] 中部分不存在，那么我们只需要检查这两个条件中的一个（或不需要检查）。 举个例子，如果 i = 0，那么 A[i−1] 不存在，我们就不需要检查 A[i−1] ≤ B[j] 是否成立。 所以，我们需要做的是：
在循环搜索中，我们只会遇到三种情况：
感谢 @Quentin.chen 指出：i < m ⟹ j > 0 以及 i > 0 ⟹ j < n 始终成立，这是因为：
所以，在情况 2 和 3 中，我们不需要检查 j > 0 或是 j < n 是否成立。
Java 代码实现：
Python 代码实现：
复杂度分析
- 时间复杂度：O(log(min(m n)))，
- 首先，查找的区间是 [0 m]。 而该区间的长度在每次循环之后都会减少为原来的一半。 所以，我们只需要执行 log(m) 次循环。由于我们在每次循环中进行常量次数的操作，所以时间复杂度为 O(log(m))。 由于 m ≤ n，所以时间复杂度是 O(log(min(m n)))。
- 空间复杂度：O(1)， 我们只需要恒定的内存来存储 9 个局部变量， 所以空间复杂度为 O(1)。
