本文共 2116 字，大约阅读时间需要 7 分钟。
给定两个大小为 m 和 n 的正序数组 nums1 和 nums2。请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
合并数组并排序：将两个数组合并，排序后找到中位数。这种方法的时间复杂度为 O((m + n)log(m + n))，虽然能解决问题，但不符合高效要求。
分割数组：将每个数组分为两半，分析分割点附近的值来确定中位数。这种方法的时间复杂度为 O(min(m, n))，但仍需进一步优化。
为了进一步减少时间复杂度，采用二分法在两个数组中寻找合适的分割点。具体步骤如下：
确定总分割点数：总分割点数为 (m + n + 1) / 2。为了保证分割点的正确性，将较短的数组作为分割点的滑动范围。
二分查找分割点：在较短的数组上滑动分割点，计算对应的分割点在另一个数组中的位置。检查左右条件是否满足，若满足则确定中位数，否则调整分割点范围。
处理边界条件：若分割点取到数组首或尾，添加虚拟极端值（如负无穷和正无穷）来确保分割条件成立。
import mathclass Solution: def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float: if len(nums1) > len(nums2): return self.findMedianSortedArrays(nums2, nums1) len1 = len(nums1) len2 = len(nums2) sum_partition = (len1 + len2 + 1) // 2 left = 0 right = len1 while left <= right: partition1 = (left + right) // 2 partition2 = sum_partition - partition1 maxLeft1 = nums1[partition1 - 1] if partition1 > 0 else -math.inf minRight1 = nums1[partition1] if partition1 < len1 else math.inf maxLeft2 = nums2[partition2 - 1] if partition2 > 0 else -math.inf minRight2 = nums2[partition2] if partition2 < len2 else math.inf if maxLeft1 <= minRight2 and maxLeft2 <= minRight1: total = len1 + len2 if total % 2 == 0: return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2 else: return max(maxLeft1, maxLeft2) elif maxLeft2 > minRight1: left = partition1 + 1 else: right = partition1 - 1 raise RuntimeError("No valid partition found") 交换数组长度：为了简化处理，将数组长度较长的作为第二个数组，较短的作为第一个数组。
确定总分割点：计算总分割点数 sum_partition，用于确定分割点的范围。
二分查找：在较短数组上滑动分割点，计算对应的分割点在另一个数组中的位置。检查左右条件是否满足。
处理分割点：根据分割点计算左右极端值，并检查是否满足中位数条件。如果满足，返回中位数；否则调整分割点范围。
边界处理：通过虚拟极端值处理分割点取到数组首或尾的情况，确保分割条件成立。
时间复杂度：通过二分法减少了不必要的线性搜索，时间复杂度降为 O(log(min(m, n)))。
空间复杂度：仅使用常数空间，适合大数组处理。
这种方法充分利用了两个数组的有序性，显著提高了计算效率，确保在合理时间内解决问题。
转载地址：http://hwhlz.baihongyu.com/