如何有效地在输入的n个元素中找到最大值和最小值？

在n个元素中寻找最大值和最小值有几种常见算法，这里列举两种基本的方法：

1. **线性扫描**：这是最直接的方式，遍历整个数组一次。从第一个元素开始，每次比较当前元素与已知的最大值（初始化为第一个元素）和最小值（初始化为第一个元素），如果当前元素更大，则更新最大值；如果更小，则更新最小值。这个过程持续到所有元素都被检查过。

def find_min_max(arr):
    if len(arr) == 0:
        return None, None
    min_val = max_val = arr[0]
    for num in arr[1:]:
        if num < min_val:
            min_val = num
        elif num > max_val:
            max_val = num
    return min_val, max_val

2. **分治法**（如二分查找用于找最大值/最小值，适用于有序数组）：对于有序数组，可以先找出中间值（中位数），然后根据中间值把数组分为两部分，分别在左半部分和右半部分中查找最大值和最小值。这是一种更快的方法，时间复杂度接近O(log n)，但对于无序数组效率不如第一种。

def find_min_max_sorted(arr):
    if len(arr) == 0:
        return None, None
    mid = len(arr) // 2
    min_val = arr[mid] if arr[mid] <= arr[mid - 1] else arr[mid - 1]
    max_val = arr[mid] if arr[mid] >= arr[mid + 1] else arr[mid + 1]
    if len(arr) % 2 != 0:
        # 如果数组长度是奇数，处理未比较的那个元素
        half_len = len(arr) // 2
        if arr[half_len] < min_val:
            min_val = arr[half_len]
        elif arr[half_len] > max_val:
            max_val = arr[half_len]
    return min_val, max_val