最有效地查找数组中的最小值

Question

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

Answer 1

如果它们没有被排序,你不能做多少但是看看每一个,即O(N),当你完成后你就会知道最小值.

伪代码:

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

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

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

以上内容在算法标题中包含为std :: min_element.

如果您可以在添加项目时对阵列进行排序,那么找到它将是O(1),因为您可以保持最小的位置.

这与数组一样好.

Answer 2

stl包含一系列应该依赖于问题的方法.

std::find
std::find_if
std::count
std::find
std::binary_search
std::equal_range
std::lower_bound
std::upper_bound

现在它包含您的数据使用的算法.这个Artikel包含一个完美的表格,以帮助选择正确的算法.

在特殊情况下,应确定min max并使用std :: vector或???*array

std::min_element
std::max_element

可以使用.

Answer 3

如果您想要真正有效并且有足够的时间花费,请使用SIMD指令.

您可以在一条指令中比较几对:

r0 := min(a0, b0)
r1 := min(a1, b1)
r2 := min(a2, b2)
r3 := min(a3, b3)
__m64 _mm_min_pu8(__m64 a , __m64 b );

今天每台计算机都支持它.其他已经为你编写了min函数:

或使用已经准备好的库.

Answer 4

你需要在数组中循环,记住你到目前为止看到的最小值.像这样:

int smallest = INT_MAX;
for (int i = 0; i < array_length; i++) {
    if (array[i] < smallest) {
        smallest = array[i];
    }
}