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

Question

Let's say I have an Array of numbers: [2,3,3,4,2,2,5,6,7,2]

What is the best way to find the minimum or maximum value in that Array?

Right now, to get the maximum, I am looping through the Array, and resetting a variable to the value if it is greater than the existing value:

var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];

var maxValue:Number = 0;

for each (var num:Number in myArray)
{
    if (num > maxValue)
        maxValue = num;
}

This just doesn't seem like the best performing way to do this (I try to avoid loops whenever possible).

Solution 1

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.

Solution 2

There isn't any reliable way to get the minimum/maximum without testing every value. You don't want to try a sort or anything like that, walking through the array is O(n), which is better than any sort algorithm can do in the general case.

Solution 3

Unless the array is sorted, that's the best you're going to get. If it is sorted, just take the first and last elements.

Of course, if it's not sorted, then sorting first and grabbing the first and last is guaranteed to be less efficient than just looping through once. Even the best sorting algorithms have to look at each element more than once (an average of O(log N) times for each element. That's O(N*Log N) total. A simple scan once through is only O(N).

If you are wanting quick access to the largest element in a data structure, take a look at heaps for an efficient way to keep objects in some sort of order.

Solution 4

You have to loop through the array, no other way to check all elements. Just one correction for the code - if all elements are negative, maxValue will be 0 at the end. You should initialize it with the minimum possible value for integer.
And if you are going to search the array many times it's a good idea to sort it first, than searching is faster (binary search) and minimum and maximum elements are just the first and the last.

Solution 5

Depends on what you call "best." From a theoretical point of view, you cannot solve the problem in less than O(n) in a deterministic Turing machine.

The naive algorithm is too loop and update min, max. However, a recursive solution will require less comparisons than naive algorithm, if you want to get min, max simultaneously (it isn't necessarily faster due to function call overhead).

struct MinMax{
   public int Min,Max;
}

MinMax FindMinMax(int[] array, int start, int end) {
   if (start == end)
      return new MinMax { Min = array[start], Max = array[start] };

   if (start == end - 1)
      return new MinMax { Min = Math.Min(array[start], array[end]), Max = Math.Max(array[start], array[end]) } ;

   MinMax res1 = FindMinMax(array, start, (start + end)/2);
   MinMax res2 = FindMinMax(array, (start+end)/2+1, end);
   return new MinMax { Min = Math.Min(res1.Min, res2.Min), Max = Math.Max(res1.Max, res2.Max) } ;
}

The simplest solution would be to sort and get the first and last item, though it's obviously not the fastest ;)

The best solution, performance-wise, to find the minimum or maximum is the naive algorithm you written (with a single loop).

View more solutions

Comments

[TravisO]

Sort may be simple but definitely not the most efficient.

[mmx]

Of course, I didn't say so! Best is not the most efficient, however!

[Eric Belair]

I would think a sort would be more efficient than a loop?

[Till F.]

I have to disagree that this has fewer comparisons than a "naive" iteration. You are comparing every element anyway, why complicate it further?

[Eric Belair]

This is exactly what I decided to do - sort the Array (descending for MAX, ascending for MIN), and then grab the first element.

[Till F.]

@Eric a sort will require you to spend however long the sort algorithm takes (greater than O(n)) whereas an intelligent loop will be O(n) in length

[mekanik]

You do realize that sorting takes way more time than simply scanning the list once.

[Till F.]

there's no need to resort the array every time if you do sorting at insertion. Then you only need to take the first/last element for min/max values.

[mekanik]

If that's the case, then it may be more efficient.

[warren]

better yet - presume the first element is both the max and min, until proven otherwise

[warren]

how do you know what the "last" item is? Unless you have a fixed-length array, and not some funky vector class or something, you may not know where it ends

[Nick Johnson]

Even if your insertion is O(log n), you're still doing more work by keeping it sorted.

[Nick Johnson]

Addendum: That is, assuming you don't need to regularly ask for the largest element - in which case keeping it sorted or using a heap is a better approach.

[mmx]

@Matthew: if you need to compute both minimum and maximum, you have to make 2n-2 comparisons in naive iteration (n-1 comparisons for each one). With this algorithm you do 3n/2 comparisons.

[mmx]

@warren: vector's end is: v[v.size()-1]

[mmx]

@Eric: I didn't mean sort is more efficient. I said he wants the best method. I meant the best method is not always the fastest. Of course a sort would take more time. But it's one line of code. So it might be the best in that regard ;)

[Zach Langley]

Your answer suggests that all sorting algorithms at their best are O(nlogn), however, that is only true for comparison sorts. You can sort an array of integral types in O(n). Regardless, for retrieving the min or max, one loop over the array is fastest.

[mekanik]

With a limited domain, you can do counting sorts that essentially boil down to preassigning slots in a large aray, going through the list once and putting each item in its pre-ordained slot, then going through the slots and putting things back in the array in order. Or a variant of that idea.

[keyle]

Math operations are notoriously slow in Flash. I'm wondering if it's actually proven to be faster this way or just an assumption?

[laurent]

Yes maybe it's faster, then again maybe it's not. I think this answer would be much better with an actual comparison of the two methods.

[jauboux]

Math.max is not native, it's running inside AVM2. It is indeed a lot slower (3x) than a for() loop on Vector.<Number>. You can have a look at my answer for more details.

[Vitaly]

I just checked this and the JavaScript version appears to be almost an order of magnitude faster in Chrome, significantly faster in Firefox and 3 times slower in Safari, compared to native: jsperf.com/math-min-max-vs-js-min-max Calling a function via apply is known to perform poorly compared to a normal function call.