【python中寻找两个有序数组的中位数】

前言：

在计算机科学和数据处理领域，寻找两个有序数组的中位数是一个关键而常见的问题。这个问题不仅仅考验着算法的效率，更涉及到对数组和排序的深刻理解。在Python这样灵活而强大的编程语言中，我们有机会通过优雅而高效的代码解决这个问题。本文将引导您深入了解在两个有序数组中寻找中位数的各种方法，以及它们的实现原理。无论您是刚刚踏入编程领域还是经验丰富的开发者，这篇博客都将为您提供有益的见解。

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3] 　　　　nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2] 　　　　nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

参考】

【leetcode】题解【1】

【实践】

【1】方法一：直接法

（1）Python

【python技巧】“&”、“>>”等

from typing import List


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)
        nums1.extend(nums2)

        nums1.sort()

        if (m + n) & 1: # & 是二进制的与操作，a & 1 相当于判断a是否是奇数
            return nums1[(m + n - 1) >> 1] # >> 是二进制右移一位，相当于除以2
        else:
            return (nums1[(m + n - 1) >> 1] + nums1[(m + n) >> 1]) / 2

【leetcode的其他算法】

【以上一些算法的时间复杂度都达不到题目的要求 O(log(m+n)

O(log(m+n)。看到 log，很明显，我们只有用到二分的方法才能达到。我们不妨用另一种思路，题目是求中位数，其实就是求第 k 小数的一种特殊情况，而求第 k 小数有一种算法。】

【参考（解法三不错）】【https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/】

在Python中寻找两个有序数组的中位数是一个涉及算法和数据结构的关键问题。以下是几种常见的方法：

归并排序合并：

这种方法涉及将两个有序数组合并为一个有序数组，然后找到中间的元素或元素对。这是因为在有序数组中，中间的元素（或元素对）即为中位数。 在Python中，您可以使用归并排序的思想，逐个比较两个数组的元素，将较小的元素添加到结果数组中，直到找到中位数为止。 二分查找：

对于有序数组，可以通过二分查找的方式找到中位数。首先，确定两个数组的中间位置，然后比较中间位置的元素，根据比较结果缩小搜索范围，直到找到中位数。 该方法适用于有序数组，时间复杂度为O(log(min(m, n)))，其中m和n分别是两个数组的长度。 直接计算中位数位置：

如果我们知道两个数组的长度和，以及中位数在整个数组中的位置，我们可以直接计算中位数的位置，然后定位到对应的元素。 对于偶数个元素的情况，中位数为两个中间元素的平均值。 使用内置函数：

Python提供了一些内置函数，例如sorted()，可以将两个有序数组合并并排序。然后，可以轻松找到中位数。 这种方法简单明了，但可能不是最优解，尤其对于大型数组而言。

结尾：

在本文中，我们探讨了在Python中寻找两个有序数组的中位数的多种方法，包括归并排序、二分查找等。这些方法不仅为解决这一具体问题提供了思路，更展示了算法设计和代码实现的精髓。通过深入理解这些技术，我们能够更好地应对类似的问题，并在实际应用中写出更高效、可维护的代码。希望本文能够为您在Python中处理有序数组的挑战提供清晰的指导，并激发您对算法优化的兴趣。感谢您的阅读，期待您在编码的旅途中取得更多的成功！