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).

Answer 1

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.

Answer 2

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.

Answer 3

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).

Answer 4

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.

Answer 5

If you are building the array once and want to find the maximum just once, iterating is the best you can do.

When you want to modify the array and occasionally want to know the maximum element, you should use a Priority Queue. One of the best data structures for that is a Fibonacci Heap, if this is too complicated use a Binary Heap which is slower but still good.

To find minimum and maximum, just build two heaps and change the sign of the numbers in one of them.

Answer 6

This depends on real world application requirements.

If your question is merely hypothetical, then the basics have already been explained. It is a typical search vs. sort problem. It has already been mentioned that algorithmically you are not going to achieve better than O(n) for that case.

However, if you are looking at practical use, things get more interesting. You would then need to consider how large the array is, and the processes involved in adding and removing from the data set. In these cases, it can be best to take the computational 'hit' at insertion / removal time by sorting on the fly. Insertions into a pre-sorted array are not that expensive.

The quickest query response to the Min Max request will always be from a sorted array, because as others have mentioned, you simply take the first or last element - giving you an O(1) cost.

For a bit more of a technical explanation on the computational costs involved, and Big O notation, check out the Wikipedia article here.

Nick.

Answer 7

If you want to find both the min and max at the same time, the loop can be modified as follows:

int min = int.maxValue;
int max = int.minValue;

foreach num in someArray {
  if(num < min)
    min = num;
  if(num > max)
    max = num;
}

This should get achieve O(n) timing.

Answer 8

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.

Answer 9

After reading everyone's comments (thank you for your interest), I found that the "best" way (least amount of code, best performing) to do this was to simply sort the Array, and then grab the first value in the Array:

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

myArray.sort(Array.NUMERIC);

var minValue:int = myArray[0];

This also works for an Array of Objects - you simply use the Array.sortOn() function and specify a property:

// Sample data
var myArray:Array /* of XML */ = 
    [
    <item level="2" name="a" />
    <item level="3" name="b" />
    <item level="3" name="c" />
    <item level="2" name="d" />
    <item level="5" name="e" />
    ]

// Perform a descending sort on the specified attribute in Array to get the maximum value
myArray.sortOn("@level", Array.DESCENDING | Array.NUMERIC);

var lowestLevel:int = myArray[0].@level;

I hope this helps someone else someday!

Answer 10

Please take into account that sorting the array will only be faster that looping up to certain size of the array. If your array is small (and it will be like that any time) then your solution is perfectly fine. But if it might get too large you should use a conditional to use the sort approach when the array is small, and the normal iteration when it is too large

Answer 11

If

1. The array is not sorted
2. Finding the min and max is done simultaneously

Then there is an algorithm that finds the min and max in 3n/2 number of comparisons. What one needs to do is process the elements of the array in pairs. The larger of the pair should be compared with the current max and the smaller of the pair should be compared with the current min. Also, one needs take special care if the array contains odd number of elements.

In c++ code (borrowing some code from Mehrdad).

struct MinMax{
   int Min,Max;
}

MinMax FindMinMax(int[] array, int start, int end) {
   MinMax  min_max;
   int index;
   int n = end - start + 1;//n: the number of elements to be sorted, assuming n>0
   if ( n%2 != 0 ){// if n is odd

     min_max.Min = array[start];
     min_max.Max = array[start];

     index = start + 1;
   }
   else{// n is even
     if ( array[start] < array[start+1] ){
       min_max.Min = array[start];
       min_max.Max = array[start+1];

       index = start + 2;
   }

   int big, small;
   for ( int i = index; i < n-1; i = i+2 ){
      if ( array[i] < array[i+1] ){ //one comparison
        small = array[i];
        big = array[i+1];
      }
      else{
        small = array[i+1];
        big = array[i];
      }
      if ( min_max.Min > small ){ //one comparison
        min_max.Min = small;
      }
      if ( min_max.Max < big ){ //one comparison
        min_max.Max = big;
      }
   }

   return min_max;
}

It's very easy to see that the number of comparisons it takes is 3n/2. The loop runs n/2 times and in each iteration 3 comparisons are performed. This is probably the optimum one can achieve. At this moment, I cannot point to a definite source of that. (But, I think I have seen a proof of that somewhere.)

The recursive solution given by Mehrdad above, probably also achieves this minimal number of comparisons (the last line needs to be changed). But with the same number of comparisons an iterative solution will always beat a recursive solution due to overhead in the function call as he mentioned. However, if one only cares about finding min and max of a few numbers (as Eric Belair does), no one will notice any difference in todays computer with any of the approaches above. For a large array, the difference could be significant.

Though this solution and the solution given by Matthew Brubaker has O(n) complexity, in practice one should carefully asses the hidden constants involved. The number of comparisons in his solution is 2n. The speedup gained with the solution with 3n/2 comparisons as opposed to 2n comparisons would be noticeable.

Answer 12

Hi,Sorry this is the closest subject i could find to post this. I'm a bit new to flex and cannot get my head around this problem. can someone help. thanks in advance.

I have a string list path. path 1 - "one/two/three" path 2 - "one/two/four" path 3 - "five/six"

i need an advanced datagrid to show a tree structure like so one/ ...two/ ........three/ ............four five/ .......six but i want to achieve this dynamicall with arrays, objects, or arraycollection (as applicable) I need to loop through each string path using string methods which isnt a problem but how do i create "DYNAMIC" (depth) children? please help as i'm about to pull my hair out.