Finding smallest value in an array most efficiently


Question

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

1
30
9/18/2012 5:07:28 PM

Accepted Answer

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.


Pseudo-code:

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

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

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


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.

That's as good as it gets with arrays.

37
5/23/2017 12:26:42 PM

The stl contains a bunch of methods that should be used dependent to the problem.

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

Now it contains on your data what algorithm to use. This Artikel contains a perfect table to help choosing the right algorithm.


In the special case where min max should be determined and you are using std::vector or ???* array

std::min_element
std::max_element

can be used.


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon