python 的分治法例题

下面是一个 Python 的分治法例题：

题目：给定一个整数列表，找到其中的最大值和最小值。

解法：可以使用分治法来解决这个问题。将列表分成两个部分，分别找到左半部分的最大值和最小值以及右半部分的最大值和最小值，然后将它们合并起来得到整个列表的最大值和最小值。

代码如下：

def find_min_max(arr):
    if len(arr) == 1:
        return arr[0], arr[0]
    if len(arr) == 2:
        return (arr[0], arr[1]) if arr[0] < arr[1] else (arr[1], arr[0])
    mid = len(arr) // 2
    left_min, left_max = find_min_max(arr[:mid])
    right_min, right_max = find_min_max(arr[mid:])
    return min(left_min, right_min), max(left_max, right_max)

arr = [3, 7, 1, 9, 4, 2, 8, 5]
min_val, max_val = find_min_max(arr)
print("Min value:", min_val)
print("Max value:", max_val)

输出结果：

Min value: 1
Max value: 9

这个算法的时间复杂度是 O(nlogn)，其中 n 是列表的长度。