分治法求最大次大最小次小值Python

分治法是一种算法设计范式，它将一个问题分解成若干个规模较小的子问题，分别解决这些子问题，然后将它们的解合并起来得到原问题的解。在求最大次大、最小次小值的问题中，我们可以使用分治法来高效地找到这些值。

下面是一个使用Python实现的示例代码：

def find_second_largest_smallest(arr):
    # 辅助函数，用于递归地找到最大和次大值
    def max_min_helper(arr, left, right):
        if left == right:  # 只有一个元素
            return arr[left], float('-inf')
        elif right == left + 1:  # 只有两个元素
            if arr[left] > arr[right]:
                return arr[left], arr[right]
            else:
                return arr[right], arr[left]
        else:
            mid = (left + right) // 2
            max1, min1 = max_min_helper(arr, left, mid)
            max2, min2 = max_min_helper(arr, mid + 1, right)
            return max(max1, max2), min(min1, min2)

    n = len(arr)
    if n < 4:
        raise ValueError("数组长度至少为4")

    max_val, min_val = max_min_helper(arr, 0, n - 1)
    
    # 初始化次大和次小的值
    second_largest = float('-inf')
    second_smallest = float('inf')
    
    # 遍历数组，更新次大和次小的值
    for num in arr:
        if num != max_val and num > second_largest:
            second_largest = num
        if num != min_val and num < second_smallest:
            second_smallest = num
    
    return second_largest, second_smallest

# 测试代码
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
second_largest, second_smallest = find_second_largest_smallest(arr)
print("次大值:", second_largest)
print("次小值:", second_smallest)

这段代码首先定义了一个辅助函数`max_min_helper`，它通过分治法递归地找到数组中的最大值和最小值。然后，主函数`find_second_largest_smallest`使用这个辅助函数来找到整个数组的最大值和最小值，并进一步遍历数组以找到次大值和次小值。最后，我们通过一组测试数据来验证这个函数的正确性。