Finding Smallest Value in an Array Most Efficiently

Finding smallest value in an array most efficiently

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.

Obtain smallest value from array in Javascript?

Jon Resig illustrated in this article how this could be achieved by extending the Array prototype and invoking the underlying Math.min method which unfortunately doesn't take an array but a variable number of arguments:

Array.min = function( array ){
    return Math.min.apply( Math, array );
};

and then:

var minimum = Array.min(array);

What is the best way to get the minimum or maximum value from an Array of numbers?

The theoretical answers from everyone else are all neat, but let's be pragmatic. ActionScript provides the tools you need so that you don't even have to write a loop in this case!

First, note that Math.min() and Math.max() can take any number of arguments. Also, it's important to understand the apply() method available to Function objects. It allows you to pass arguments to the function using an Array. Let's take advantage of both:

var myArray:Array = [2,3,3,4,2,2,5,6,7,2];
var maxValue:Number = Math.max.apply(null, myArray);
var minValue:Number = Math.min.apply(null, myArray);

Here's the best part: the "loop" is actually run using native code (inside Flash Player), so it's faster than searching for the minimum or maximum value using a pure ActionScript loop.

Calculating the maximum/minimum value off an Array most efficiently in java

First of all, giving sufficiently large input, time measurement is realible enough.

Second, in your example code, neither comparisons nor write operations matter at all. Most time will be spend accessing the large array (the whole question is only relevant for large arrays, containing many millions of elements) in memory and moving it to the CPUs cache.

Third, if you want both extrema it will be best to get them while going through your array only once. This corresponds to 2*n comparision (nothing to do with n^2) and is still vastly dominated by accessing the array's data in memory.

If you need the max/min of the same array many times, just store it and dont compute it every time. Unless you need a sorted veriant of your array in another place (or you can presort it once and resue that every thime the program is run), there is no point in sorting to get min/max.

---

Related Topics