中位数问题分治法伪代码

以下是中位数问题的分治法伪代码：

def find_median(nums):
    n = len(nums)
    if n % 2 == 1:  # 如果数组元素个数是奇数
        return quick_select(nums, n // 2)  # 直接找到第 n//2 小的元素即为中位数
    else:  # 如果数组元素个数是偶数
        return (quick_select(nums, n // 2 - 1) + quick_select(nums, n // 2)) / 2  # 找到第 n//2 - 1 小和第 n//2 小的元素，取平均值作为中位数

def quick_select(nums, k):
    if len(nums) == 1:  # 如果只有一个元素，则返回该元素
        return nums[0]
    pivot = random.choice(nums)  # 随机选择一个枢轴元素
    left = [x for x in nums if x < pivot]  # 将小于枢轴的元素放到左边数组
    right = [x for x in nums if x > pivot]  # 将大于枢轴的元素放到右边数组
    mid = [x for x in nums if x == pivot]  # 将等于枢轴的元素放到中间数组
    if k < len(left):  # 如果第 k 小的元素在左边数组中，递归处理左边数组
        return quick_select(left, k)
    elif k < len(left) + len(mid):  # 如果第 k 小的元素在中间数组中，直接返回中间数组的第一个元素
        return mid[0]
    else:  # 如果第 k 小的元素在右边数组中，递归处理右边数组
        return quick_select(right, k - len(left) - len(mid))

其中，`quick_select` 函数用于找到第 k 小的元素，`find_median` 函数用于找到数组的中位数。在 `find_median` 函数中，如果数组元素个数是奇数，则直接找到第 n//2 小的元素即为中位数；如果数组元素个数是偶数，则找到第 n//2 - 1 小和第 n//2 小的元素，取平均值作为中位数。