打擂台法求最大值最小值 c++

在C++中，打擂台（Tournament）方法，也被称为“锦标赛”算法，是一种用于查找数组或列表中的最大值和最小值的高效算法。这个方法适用于没有排序的元素，并且不需要线性时间复杂度。它的基本思想是通过递归地将元素分成两组进行比赛，最终的胜者就是最大值或最小值。

以下是打擂台法求最大值和最小值的C++实现：

#include <iostream>
using namespace std;

// 比赛函数，返回较大的元素
int maxCompare(int a, int b) {
    return a > b ? a : b;
}

// 擂台法求最大值
int tournamentMax(int arr[], int low, int high) {
    if (low == high) {
        return arr[low];
    }
    int mid = (low + high) / 2;
    int leftMax = tournamentMax(arr, low, mid);
    int rightMax = tournamentMax(arr, mid + 1, high);
    return maxCompare(leftMax, rightMax);
}

// 擂台法求最小值
int tournamentMin(int arr[], int low, int high) {
    if (low == high) {
        return arr[low];
    }
    int mid = (low + high) / 2;
    int leftMin = tournamentMin(arr, low, mid);
    int rightMin = tournamentMin(arr, mid + 1, high);
    return leftMin < rightMin ? leftMin : rightMin;
}

int main() {
    int arr[] = {9, 5, 2, 7, 1, 8};
    int size = sizeof(arr) / sizeof(arr);
    int maxVal = tournamentMax(arr, 0, size - 1);
    int minVal = tournamentMin(arr, 0, size - 1);
    cout << "Max value: " << maxVal << endl;
    cout << "Min value: " << minVal << endl;
    return 0;
}