迹忆客 专注技术分享

本文将介绍如何在 C++ 中查找数组中的最大值。

使用迭代法在 C++ 数组中查找最大值

实现用于最大值搜索的自定义函数的直接方法是使用迭代方法。以下示例代码具有 for 循环结构，该结构循环遍历数组的每个元素并检查当前值是否大于当前最大值。请注意，当前最大值使用数组中第一个元素的值进行初始化，并在 if 条件评估为真时进行修改。

#include <iostream>
#include <ctime>
#include <sys/time.h>

using std::cout;
using std::endl;

void generateNumbers(int arr[], size_t &width){

    std::srand(std::time(nullptr));
    for (size_t i = 0; i < width; i++) {
        arr[i] = std::rand();
    }
}

template<typename T>
T FindMax(T *arr, size_t n)
{
    int max = arr[0];

    for (size_t j = 0; j < n; ++j) {
        if (arr[j] > max) {
            max = arr[j];
        }
    }
    return max;
}

float time_diff(struct timeval *start, struct timeval *end){
    return (end->tv_sec - start->tv_sec) + 1e-6*(end->tv_usec - start->tv_usec);
}

int main() {
    struct timeval start{};
    struct timeval end{};

    size_t width = 100000;
    int *arr = new int[width];

    generateNumbers(arr, width);

    gettimeofday(&start, nullptr);
    cout << "Maximum element is: " << FindMax(arr, width) << endl;
    gettimeofday(&end, nullptr);

    printf ("FindMax: %0.8f sec\n",
            time_diff(&start, &end));

    delete [] arr;
    return EXIT_SUCCESS;
}

输出：

Maximum element is: 2147460568
FindMax: 0.00017500 sec

使用 std::max_element 算法在 C++ 数组中查找最大值

std::max_element 是另一种在给定范围内查找最大值的方法。它是 STL 算法的一部分，最简单的重载只需要两个迭代器来表示要搜索的范围边界。std::max_element 返回一个迭代器到最大值元素。如果多个元素具有相同的值并且同时恰好是最大值，则该函数返回指向第一个元素的迭代器。

#include <iostream>
#include <ctime>
#include <sys/time.h>

using std::cout;
using std::endl;

void generateNumbers(int arr[], size_t &width){

    std::srand(std::time(nullptr));
    for (size_t i = 0; i < width; i++) {
        arr[i] = std::rand();
    }
}

template<typename T>
T FindMax2(T *arr, size_t n)
{
    return *std::max_element(arr, arr+n);
}

float time_diff(struct timeval *start, struct timeval *end){
    return (end->tv_sec - start->tv_sec) + 1e-6*(end->tv_usec - start->tv_usec);
}

int main() {
    struct timeval start{};
    struct timeval end{};

    size_t width = 100000;
    int *arr = new int[width];

    generateNumbers(arr, width);

    gettimeofday(&start, nullptr);
    cout << "Maximum element is: " << FindMax2(arr, width) << endl;
    gettimeofday(&end, nullptr);

    printf ("FindMax2: %0.8f sec\n",
            time_diff(&start, &end));

    delete [] arr;
    return EXIT_SUCCESS;
}

输出：

Maximum element is: 2147413532
FindMax2: 0.00023700 sec

使用 std::minmax_element 算法在 C++ 数组中查找最大值

或者，我们可以使用 STL 中的 std::minmax_element 算法来查找给定范围内的最小和最大元素，并将它们作为 std::pair 返回。minmax_element 函数可以选择将自定义二进制比较函数作为第三个参数。否则，它具有与 max_element 相同的参数，并且当在范围内找到多个最小/最大元素时，它的行为类似。

#include <iostream>
#include <ctime>
#include <sys/time.h>

using std::cout;
using std::endl;

void generateNumbers(int arr[], size_t &width){

    std::srand(std::time(nullptr));
    for (size_t i = 0; i < width; i++) {
        arr[i] = std::rand();
    }
}

template<typename T>
auto FindMinMax(T *arr, size_t n)
{
    return std::minmax_element(arr, arr+n);
}

float time_diff(struct timeval *start, struct timeval *end){
    return (end->tv_sec - start->tv_sec) + 1e-6*(end->tv_usec - start->tv_usec);
}

int main() {
    struct timeval start{};
    struct timeval end{};

    size_t width = 100000;
    int *arr = new int[width];

    generateNumbers(arr, width);

    gettimeofday(&start, nullptr);
    auto ret = FindMinMax(arr, width);
    gettimeofday(&end, nullptr);
    cout << "MIN element is: " << *ret.first
         << " MAX element is: " << *ret.second << endl;

    printf ("FindMinMax: %0.8f sec\n",
            time_diff(&start, &end));

    delete [] arr;
    return EXIT_SUCCESS;
}

输出：

MIN element is: 3843393 MAX element is: 2147251693
FindMinMax: 0.00000400 sec