最有效地查找数组中的最小值 [英] Finding smallest value in an array most efficiently

问题描述

数组中有N个值，其中一个是最小值.如何最有效地找到最小值?

There are N values in the array, and one of them is the smallest value. How can I find the smallest value most efficiently?

推荐答案

如果它们没有排序，你不能做太多，只能查看每一个，这是 O(N)，当你完成后你会知道最小值.

If they are unsorted, you can't do much but look at each one, which is O(N), and when you're done you'll know the minimum.

伪代码:

small = <biggest value> // such as std::numerical_limits<int>::max
for each element in array:
    if (element < small)
        small = element

Ben 提醒我的一个更好的方法是用第一个元素初始化 small:

A better way reminded by Ben to me was to just initialize small with the first element:

small = element[0]
for each element in array, starting from 1 (not 0):
    if (element < small)
        small = element

以上内容包含在 algorithm 标头中作为 std::min_element.

The above is wrapped in the algorithm header as std::min_element.

如果您可以在添加项目时保持数组排序，那么找到它的过程将是 O(1)，因为您可以将最小的放在前面.

If you can keep your array sorted as items are added, then finding it will be O(1), since you can keep the smallest at front.

这和数组一样好.

这篇关于最有效地查找数组中的最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！