分治法求数组最大值和最小值：C语言实现及比较次数分析

使用分治思想求数组最大值和最小值：C语言实现及比较次数分析

本文介绍使用分治思想设计一个程序，用于计算n个整数的最大值和最小值。程序使用 C 语言编写，在 Visual Studio 2010 版本上实现。

算法思想

1. 将 n 个整数划分为两个子问题，每个子问题中包含 n/2 个整数。
2. 递归地求解左子问题和右子问题，得到左子问题的最大值和最小值，以及右子问题的最大值和最小值。
3. 比较左子问题的最大值和右子问题的最大值，取较大值作为整体的最大值；比较左子问题的最小值和右子问题的最小值，取较小值作为整体的最小值。

程序实现

#include <stdio.h>

struct MinMax {
    int min;
    int max;
};

struct MinMax findMinMax(int arr[], int low, int high) {
    struct MinMax result, leftResult, rightResult;
    int mid;

    // 当只有一个元素时，最大值和最小值都是该元素本身
    if (low == high) {
        result.min = arr[low];
        result.max = arr[low];
        return result;
    }

    // 当有两个元素时，比较二者大小
    if (high == low + 1) {
        if (arr[low] < arr[high]) {
            result.min = arr[low];
            result.max = arr[high];
        }
        else {
            result.min = arr[high];
            result.max = arr[low];
        }
        return result;
    }

    // 分割数组并递归求解左子问题和右子问题
    mid = (low + high) / 2;
    leftResult = findMinMax(arr, low, mid);
    rightResult = findMinMax(arr, mid + 1, high);

    // 比较左子问题的最大值和右子问题的最大值
    if (leftResult.max > rightResult.max) {
        result.max = leftResult.max;
    }
    else {
        result.max = rightResult.max;
    }

    // 比较左子问题的最小值和右子问题的最小值
    if (leftResult.min < rightResult.min) {
        result.min = leftResult.min;
    }
    else {
        result.min = rightResult.min;
    }
    
    return result;
}

int main() {
    int arr[] = { 5, 3, 8, 2, 1, 7, 6, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    struct MinMax result = findMinMax(arr, 0, n - 1);

    printf('最小值：%d\n', result.min);
    printf('最大值：%d\n', result.max);

    return 0;
}

比较次数分析

在这个程序中，在每次递归中，会进行一次比较操作来确定左子问题和右子问题的最大值和最小值。每次递归都将问题规模减半，所以总的比较次数可以近似为 n/2。因此，比较的次数为 O(n)。