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  gt  maxValue          maxValue   num      This just doesn t seem like the best performing way to do this  I try to avoid loops whenever possible

User · Answer

Math max   is actually as3 code compiled to AVM2 opcodes  and as such is not more  native  than any other as3 code  As a consequence  it is not necessarily the fastest implementation   Actually  given that it works on Array type  it is slower than carefully written code usign Vector   I did a quick benchmark comparison of several naive Vector and Array implementations of Math max  using gskinner s PerformanceTest  Vector and Array being filled with identical random Numbers   The fastest Vector implementation appeared to be more than 3x faster than Math max with recent AIR SDK release player  flash player WIN 14 0 0 122 RELEASE  compiled with AIR SDK 14    average 3 5 ms for 1 000 000 values  compared to Math max   average of 11ms    function max values Vector  lt Number gt   Number       var max Number   Number MIN VALUE      var length uint   values length      for  var i uint   0  i  lt  length     i          if  values i   gt  max              max   values i       return max      Conclusion is that if you are concerned by performance  you should use Vector over Array anywhere you can in the first place  and not always rely on default implementations  especially when they force the use of Array  PS same implementation with a for each   loop is 12x slower

User · Answer

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                  lt item level  2  name  a    gt       lt item level  3  name  b    gt       lt item level  3  name  c    gt       lt item level  2  name  d    gt       lt item level  5  name  e    gt            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

User · Answer

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

User · Answer

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  lt  min      min   num    if num  gt  max      max   num      This should get achieve O n  timing

User · Answer

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

User · Answer

Math max   is actually as3 code compiled to AVM2 opcodes  and as such is not more  native  than any other as3 code  As a consequence  it is not necessarily the fastest implementation   Actually  given that it works on Array type  it is slower than carefully written code usign Vector   I did a quick benchmark comparison of several naive Vector and Array implementations of Math max  using gskinner s PerformanceTest  Vector and Array being filled with identical random Numbers   The fastest Vector implementation appeared to be more than 3x faster than Math max with recent AIR SDK release player  flash player WIN 14 0 0 122 RELEASE  compiled with AIR SDK 14    average 3 5 ms for 1 000 000 values  compared to Math max   average of 11ms    function max values Vector  lt Number gt   Number       var max Number   Number MIN VALUE      var length uint   values length      for  var i uint   0  i  lt  length     i          if  values i   gt  max              max   values i       return max      Conclusion is that if you are concerned by performance  you should use Vector over Array anywhere you can in the first place  and not always rely on default implementations  especially when they force the use of Array  PS same implementation with a for each   loop is 12x slower

User · Answer

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

User · Answer

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

User · Answer

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  lt  min      min   num    if num  gt  max      max   num      This should get achieve O n  timing

User · Answer

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

User · Answer

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

User · Answer

If   The array is not sorted 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 gt 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   lt  array start 1            min max Min   array start          min max Max   array start 1               else         min max Min   array start 1          min max Max   array start               index   start   2           int big  small     for   int i   index  i  lt  n-1  i   i 2          if   array i   lt  array i 1       one comparison         small   array i           big   array i 1                 else          small   array i 1           big   array i                 if   min max Min  gt  small      one comparison         min max Min   small                if   min max Max  lt  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

User · Answer

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

User · Answer

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

User · Answer

Amazed no-one mentioned parallelism here   If you got really a huge array  you can use parallel-for  on sub ranges  In the end compare all sub-ranges  But parallelism comes width some penalty too  so this would not optimize on small arrays  However if you got huge datasets it starts to make sense  and you get a time division reduction nearing the  amount of threads performing the test

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

Algorithm MaxMin first  last  max  min     This algorithm stores the highest and lowest element    Values of the global array A in the global variables max and min    tmax and tmin are temporary global variables     if  first  last    Sub-array contains single element        max A first       min A first       else if first 1  last    Sub-array contains two elements          if A first  lt A Last                 max a last      Second element is largest       min a first     First element is smallest            else           max a first     First element is Largest       min a last      Second element is smallest        else    sub-array contains more than two elements      Hence partition the sub-array into smaller sub-array   mid  first last  2     Recursively solve the sub-array  MaxMin first mid max min    MaxMin mid 1 last tmax tmin    if max lt tmax           max tmax          if min gt tmin         min tmin

User · Answer

Below is Solution with o n  -  public static void findMaxAndMinValue int A         int min  0  max   0      if A 0   gt  A 1             min   A 1           max   A 0        else          max   A 1           min   A 0             for int i   2 i lt A length  i             if A i   gt  max               max   A i                     if min  gt  A i                min   A i                       System out println  Maxinum Value is    min    amp  Minimum Value is    max

User · Answer

Find max values from a array Let s see how to obtain min  max values by using a single funtion  public void findMaxValue       int   my array    1 2  6 5 8 3 9 0 23      int max   my array 0      for int i 1  i lt my array length  i               if my array i   gt  max           max   my array i           return max       same thing can do for find min value

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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                  lt item level  2  name  a    gt       lt item level  3  name  b    gt       lt item level  3  name  c    gt       lt item level  2  name  d    gt       lt item level  5  name  e    gt            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

User · Answer

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

User · Answer

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  lt  min      min   num    if num  gt  max      max   num      This should get achieve O n  timing

User · Answer

There are a number of ways this can be done    Brute force  Linear search for both min and max separately   2N comparisons and 2N steps   Iterate linearly and check each number for both min and max   2N comparisons    Use Divide and conquer   Between 2N and 3N 2 comparisons   Compare by pairs explained below  3N 2 Comparisons    How to find max  and min  in array using minimum comparisons     If you are really paranoid about speed  runtime  amp  number of comparisons  also refer to http   www geeksforgeeks org maximum-and-minimum-in-an-array

User · Answer

Shortest way     Math min apply null array     this will return min value from array   Math max apply null array     this will return max value from array     otherway of getting min  amp  max value from array   function maxVal givenArray  Number           var max   givenArray 0       for  var ma int   0  ma lt givenArray length  ma              if  givenArray ma   gt  max            max   givenArray ma                   return max             function minVal givenArray  Number           var min   givenArray 0       for  var mi int   0  mi lt givenArray length  mi              if  givenArray mi   lt  min            min   givenArray mi                   return min          As you can see  the code in both of these functions is very similar  The function sets a variable - max  or min  and then runs through the array with a loop  checking each next element  If the next element is higher than the current  set it to max  or min   In the end  return the number

User · Answer

Find max values from a array Let s see how to obtain min  max values by using a single funtion  public void findMaxValue       int   my array    1 2  6 5 8 3 9 0 23      int max   my array 0      for int i 1  i lt my array length  i               if my array i   gt  max           max   my array i           return max       same thing can do for find min value

User · Answer

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  lt  min      min   num    if num  gt  max      max   num      This should get achieve O n  timing

User · Answer

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

User · Answer

Shortest way     Math min apply null array     this will return min value from array   Math max apply null array     this will return max value from array     otherway of getting min  amp  max value from array   function maxVal givenArray  Number           var max   givenArray 0       for  var ma int   0  ma lt givenArray length  ma              if  givenArray ma   gt  max            max   givenArray ma                   return max             function minVal givenArray  Number           var min   givenArray 0       for  var mi int   0  mi lt givenArray length  mi              if  givenArray mi   lt  min            min   givenArray mi                   return min          As you can see  the code in both of these functions is very similar  The function sets a variable - max  or min  and then runs through the array with a loop  checking each next element  If the next element is higher than the current  set it to max  or min   In the end  return the number

User · Answer

Algorithm MaxMin first  last  max  min     This algorithm stores the highest and lowest element    Values of the global array A in the global variables max and min    tmax and tmin are temporary global variables     if  first  last    Sub-array contains single element        max A first       min A first       else if first 1  last    Sub-array contains two elements          if A first  lt A Last                 max a last      Second element is largest       min a first     First element is smallest            else           max a first     First element is Largest       min a last      Second element is smallest        else    sub-array contains more than two elements      Hence partition the sub-array into smaller sub-array   mid  first last  2     Recursively solve the sub-array  MaxMin first mid max min    MaxMin mid 1 last tmax tmin    if max lt tmax           max tmax          if min gt tmin         min tmin

User · Answer

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

User · Answer

Below is Solution with o n  -  public static void findMaxAndMinValue int A         int min  0  max   0      if A 0   gt  A 1             min   A 1           max   A 0        else          max   A 1           min   A 0             for int i   2 i lt A length  i             if A i   gt  max               max   A i                     if min  gt  A i                min   A i                       System out println  Maxinum Value is    min    amp  Minimum Value is    max

User · Answer

If   The array is not sorted 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 gt 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   lt  array start 1            min max Min   array start          min max Max   array start 1               else         min max Min   array start 1          min max Max   array start               index   start   2           int big  small     for   int i   index  i  lt  n-1  i   i 2          if   array i   lt  array i 1       one comparison         small   array i           big   array i 1                 else          small   array i 1           big   array i                 if   min max Min  gt  small      one comparison         min max Min   small                if   min max Max  lt  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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

Amazed no-one mentioned parallelism here   If you got really a huge array  you can use parallel-for  on sub ranges  In the end compare all sub-ranges  But parallelism comes width some penalty too  so this would not optimize on small arrays  However if you got huge datasets it starts to make sense  and you get a time division reduction nearing the  amount of threads performing the test

User · Answer

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

User · Answer

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

User · Answer

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                  lt item level  2  name  a    gt       lt item level  3  name  b    gt       lt item level  3  name  c    gt       lt item level  2  name  d    gt       lt item level  5  name  e    gt            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

User · Answer

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

User · Answer

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

User · Answer

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                  lt item level  2  name  a    gt       lt item level  3  name  b    gt       lt item level  3  name  c    gt       lt item level  2  name  d    gt       lt item level  5  name  e    gt            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

User · Answer

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

User · Answer

There are a number of ways this can be done    Brute force  Linear search for both min and max separately   2N comparisons and 2N steps   Iterate linearly and check each number for both min and max   2N comparisons    Use Divide and conquer   Between 2N and 3N 2 comparisons   Compare by pairs explained below  3N 2 Comparisons    How to find max  and min  in array using minimum comparisons     If you are really paranoid about speed  runtime  amp  number of comparisons  also refer to http   www geeksforgeeks org maximum-and-minimum-in-an-array

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

Examples related to algorithm

Examples related to actionscript-3

Examples related to apache-flex

Examples related to actionscript

Examples related to complexity-theory