Массив как найти max

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.

answered Jan 8, 2009 at 23:51

Adam BellaireAdam Bellaire

107k19 gold badges148 silver badges163 bronze badges

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];
     }
     else{
       min_max.Min = array[start+1];
       min_max.Max = array[start];
     }
     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.

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.

answered Jan 8, 2009 at 16:10

answered Jan 8, 2009 at 16:03

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

answered Jan 8, 2009 at 16:06

jaubouxjauboux

8886 silver badges12 bronze badges

NickNick

2,2852 gold badges14 silver badges26 bronze badges

martinusmartinus

17.7k15 gold badges72 silver badges92 bronze badges

Matthew BrubakerMatthew Brubaker

3,0971 gold badge21 silver badges18 bronze badges

sajansajan

1,3451 gold badge14 silver badges18 bronze badges

Ajay KumarAjay Kumar

4,6481 gold badge38 silver badges42 bronze badges

PeterPeter

2,0071 gold badge20 silver badges45 bronze badges

Eric BelairEric Belair

10.6k13 gold badges75 silver badges116 bronze badges

How about augmenting the built-in Array object to use Math.max/Math.min instead:

Array.prototype.max = function() {
  return Math.max.apply(null, this);
};

Array.prototype.min = function() {
  return Math.min.apply(null, this);
};

let p = [35,2,65,7,8,9,12,121,33,99];

console.log(`Max value is: ${p.max()}` +
  `nMin value is: ${p.min()}`);

Here is a JSFiddle.

Augmenting the built-ins can cause collisions with other libraries (some see), so you may be more comfortable with just apply‘ing Math.xxx() to your array directly:

var min = Math.min.apply(null, arr),
    max = Math.max.apply(null, arr);

Alternately, assuming your browser supports ECMAScript 6, you can use spread syntax which functions similarly to the apply method:

var min = Math.min( ...arr ),
    max = Math.max( ...arr );

Using spread operator (ES6)

Math.max(...array)  // The same with "min" => Math.min(...array)

For big arrays (~10⁷ elements), Math.min and Math.max both produces the following error in Node.js.

RangeError: Maximum call stack size exceeded

A more robust solution is to not add every element to the call stack, but to instead pass an array:

function arrayMin(arr) {
  return arr.reduce(function (p, v) {
    return ( p < v ? p : v );
  });
}

function arrayMax(arr) {
  return arr.reduce(function (p, v) {
    return ( p > v ? p : v );
  });
}

If you are concerned about speed, the following code is ~3 times faster then Math.max.apply is on my computer. See https://jsben.ch/JPOyL.

function arrayMin(arr) {
  var len = arr.length, min = Infinity;
  while (len--) {
    if (arr[len] < min) {
      min = arr[len];
    }
  }
  return min;
};

function arrayMax(arr) {
  var len = arr.length, max = -Infinity;
  while (len--) {
    if (arr[len] > max) {
      max = arr[len];
    }
  }
  return max;
};

If your arrays contains strings instead of numbers, you also need to coerce them into numbers. The below code does that, but it slows the code down ~10 times on my machine. See https://jsben.ch/uPipD.

function arrayMin(arr) {
  var len = arr.length, min = Infinity;
  while (len--) {
    if (Number(arr[len]) < min) {
      min = Number(arr[len]);
    }
  }
  return min;
};

function arrayMax(arr) {
  var len = arr.length, max = -Infinity;
  while (len--) {
    if (Number(arr[len]) > max) {
      max = Number(arr[len]);
    }
  }
  return max;
};

tl;dr

// For regular arrays:
var max = Math.max(...arrayOfNumbers);

// For arrays with tens of thousands of items:
let max = testArray[0];
for (let i = 1; i < testArrayLength; ++i) {
  if (testArray[i] > max) {
    max = testArray[i];
  }
}

MDN solution

The official MDN docs on Math.max() already covers this issue:

The following function uses Function.prototype.apply() to find the maximum element in a numeric array. getMaxOfArray([1, 2, 3]) is equivalent to Math.max(1, 2, 3), but you can use getMaxOfArray() on programmatically constructed arrays of any size.

function getMaxOfArray(numArray) {
    return Math.max.apply(null, numArray);
}

Or with the new spread operator, getting the maximum of an array becomes a lot easier.

var arr = [1, 2, 3];
var max = Math.max(...arr);

Maximum size of an array

According to MDN the apply and spread solutions had a limitation of 65536 that came from the limit of the maximum number of arguments:

But beware: in using apply this way, you run the risk of exceeding the JavaScript engine’s argument length limit. The consequences of applying a function with too many arguments (think more than tens of thousands of arguments) vary across engines (JavaScriptCore has hard-coded argument limit of 65536), because the limit (indeed even the nature of any excessively-large-stack behavior) is unspecified. Some engines will throw an exception. More perniciously, others will arbitrarily limit the number of arguments actually passed to the applied function. To illustrate this latter case: if such an engine had a limit of four arguments (actual limits are of course significantly higher), it would be as if the arguments 5, 6, 2, 3 had been passed to apply in the examples above, rather than the full array.

They even provide a hybrid solution which doesn’t really have good performance compared to other solutions. See performance test below for more.

In 2019 the actual limit is the maximum size of the call stack. For modern Chromium based desktop browsers this means that when it comes to finding min/max with apply or spread, practically the maximum size for numbers only arrays is ~120000. Above this, there will be a stack overflow and the following error will be thrown:

RangeError: Maximum call stack size exceeded

With the script below (based on this blog post), by catching that error you can calculate the limit for your specific environment.

Warning! Running this script takes time and depending on the performance of your system it might slow or crash your browser/system!

let testArray = Array.from({length: 10000}, () => Math.floor(Math.random() * 2000000));
for (i = 10000; i < 1000000; ++i) {
  testArray.push(Math.floor(Math.random() * 2000000));
  try {
    Math.max.apply(null, testArray);
  } catch (e) {
    console.log(i);
    break;
  }
}

Performance on large arrays

Based on the test in EscapeNetscape’s comment I created some benchmarks that tests 5 different methods on a random number only array with 100000 items.

In 2019, the results show that the standard loop (which BTW doesn’t have the size limitation) is the fastest everywhere. apply and spread comes closely after it, then much later MDN’s hybrid solution then reduce as the slowest.

Almost all tests gave the same results, except for one where spread somewhy ended up being the slowest.

If you step up your array to have 1 million items, things start to break and you are left with the standard loop as a fast solution and reduce as a slower.

JSPerf benchmark

JSBen benchmark

JSBench.me benchmark

Benchmark source code

answered Jun 14, 2015 at 21:22

If you’re paranoid like me about using Math.max.apply (which could cause errors when given large arrays according to MDN), try this:

function arrayMax(array) {
  return array.reduce(function(a, b) {
    return Math.max(a, b);
  });
}

function arrayMin(array) {
  return array.reduce(function(a, b) {
    return Math.min(a, b);
  });
}

Or, in ES6:

function arrayMax(array) {
  return array.reduce((a, b) => Math.max(a, b));
}

function arrayMin(array) {
  return array.reduce((a, b) => Math.min(a, b));
}

The anonymous functions are unfortunately necessary (instead of using Math.max.bind(Math) because reduce doesn’t just pass a and b to its function, but also i and a reference to the array itself, so we have to ensure we don’t try to call max on those as well.

answered Jul 27, 2015 at 1:00

Alternative Methods

const arr = Array.from(Array(1000000).keys());
Math.min(arr);
Math.max(arr);

Uncaught RangeError: Maximum call stack size exceeded

UPDATE
Latest browsers might return NaN instead. That might be a better way to handle errors, however it doesn’t solve the problem just yet.

Instead, consider using something like so:

function maxValue(arr) {
  return arr.reduce((max, val) => max > val ? max : val)
}

Or with better run-time:

function maxValue(arr) {
  let max = arr[0];

  for (let val of arr) {
    if (val > max) {
      max = val;
    }
  }
  return max;
}

Or to get both Min and Max:

function getMinMax(arr) {
  return arr.reduce(({min, max}, v) => ({
    min: min < v ? min : v,
    max: max > v ? max : v,
  }), { min: arr[0], max: arr[0] });
}

Or with even better run-time*:

function getMinMax(arr) {
  let min = arr[0];
  let max = arr[0];
  let i = arr.length;
    
  while (i--) {
    min = arr[i] < min ? arr[i] : min;
    max = arr[i] > max ? arr[i] : max;
  }
  return { min, max };
}

* Tested with 1,000,000 items:
Just for a reference, the 1st function run-time (on my machine) was 15.84ms vs 2nd function with only 4.32ms.

answered Oct 2, 2018 at 17:34

Two ways are shorter and easy:

let arr = [2, 6, 1, 0]

Way 1:

let max = Math.max.apply(null, arr)

Way 2:

let max = arr.reduce(function(a, b) {
    return Math.max(a, b);
});

answered May 18, 2018 at 1:37

.apply is often used when the intention is to invoke a variadic function with a list of argument values, e.g.

The Math.max([value1[,value2, ...]]) function returns the largest of zero or more numbers.

Math.max(10, 20); // 20
Math.max(-10, -20); // -10
Math.max(-10, 20); // 20

The Math.max() method doesn’t allow you to pass in an array. If you have a list of values of which you need to get the largest, you would normally call this function using Function.prototype.apply(), e.g.

Math.max.apply(null, [10, 20]); // 20
Math.max.apply(null, [-10, -20]); // -10
Math.max.apply(null, [-10, 20]); // 20

However, as of the ECMAScript 6 you can use the spread operator:

The spread operator allows an expression to be expanded in places where multiple arguments (for function calls) or multiple elements (for array literals) are expected.

Using the spread operator, the above can be rewritten as such:

Math.max(...[10, 20]); // 20
Math.max(...[-10, -20]); // -10
Math.max(...[-10, 20]); // 20

When calling a function using the variadic operator, you can even add additional values, e.g.

Math.max(...[10, 20], 50); // 50
Math.max(...[-10, -20], 50); // 50

Bonus:

Spread operator enables you to use the array literal syntax to create new arrays in situations where in ES5 you would need to fall back to imperative code, using a combination of push, splice, etc.

let foo = ['b', 'c'];
let bar = ['a', ...foo, 'd', 'e']; // ['a', 'b', 'c', 'd', 'e']

answered Dec 18, 2014 at 1:38

brettkellybrettkelly

27.6k8 gold badges56 silver badges71 bronze badges

A simple solution to find the minimum value over an Array of elements is to use the Array prototype function reduce:

A = [4,3,-9,-2,2,1];
A.reduce((min, val) => val < min ? val : min, A[0]); // returns -9

or using JavaScript’s built-in Math.Min() function (thanks @Tenflex):

A.reduce((min,val) => Math.min(min,val), A[0]);

This sets min to A[0], and then checks for A[1]...A[n] whether it is strictly less than the current min. If A[i] < min then min is updated to A[i]. When all array elements has been processed, min is returned as the result.

EDIT: Include position of minimum value:

A = [4,3,-9,-2,2,1];
A.reduce((min, val) => val < min._min ? {_min: val, _idx: min._curr, _curr: min._curr + 1} : {_min: min._min, _idx: min._idx, _curr: min._curr + 1}, {_min: A[0], _idx: 0, _curr: 0}); // returns { _min: -9, _idx: 2, _curr: 6 }

answered Oct 29, 2017 at 11:26

let array = [100, 0, 50];
let [min, max] = array.reduce(([prevMin,prevMax], curr)=>
   [Math.min(prevMin, curr), Math.max(prevMax, curr)], [Infinity, -Infinity]);
console.log("Min:", min);
console.log("Max:", max);

const arr = [-1, 9, 3, -6, 35];

//Only find minimum
const min = arr.reduce((a,b)=>Math.min(a,b), Infinity);
console.log("Min:", min);//-6

//Only find maximum
const max = arr.reduce((a,b)=>Math.max(a,b), -Infinity);
console.log("Max:", max);//35

UnmitigatedUnmitigated

69.5k8 gold badges56 silver badges76 bronze badges

Others have already given some solutions in which they augment Array.prototype. All I want in this answer is to clarify whether it should be Math.min.apply( Math, array ) or Math.min.apply( null, array ). So what context should be used, Math or null?

When passing null as a context to apply, then the context will default to the global object (the window object in the case of browsers). Passing the Math object as the context would be the correct solution, but it won’t hurt passing null either. Here’s an example when null might cause trouble, when decorating the Math.max function:

// decorate Math.max
(function (oldMax) {
    Math.max = function () {
        this.foo(); // call Math.foo, or at least that's what we want

        return oldMax.apply(this, arguments);
    };
})(Math.max);

Math.foo = function () {
    print("foo");
};

Array.prototype.max = function() {
  return Math.max.apply(null, this); // <-- passing null as the context
};

var max = [1, 2, 3].max();

print(max);

The above will throw an exception because this.foo will be evaluated as window.foo, which is undefined. If we replace null with Math, things will work as expected and the string “foo” will be printed to the screen (I tested this using Mozilla Rhino).

You can pretty much assume that nobody has decorated Math.max so, passing null will work without problems.

answered Nov 3, 2009 at 18:39

One more way to do it:

var arrayMax = Function.prototype.apply.bind(Math.max, null);

Usage:

var max = arrayMax([2, 5, 1]);

This may suit your purposes.

Array.prototype.min = function(comparer) {

    if (this.length === 0) return null;
    if (this.length === 1) return this[0];

    comparer = (comparer || Math.min);

    var v = this[0];
    for (var i = 1; i < this.length; i++) {
        v = comparer(this[i], v);    
    }

    return v;
}

Array.prototype.max = function(comparer) {

    if (this.length === 0) return null;
    if (this.length === 1) return this[0];

    comparer = (comparer || Math.max);

    var v = this[0];
    for (var i = 1; i < this.length; i++) {
        v = comparer(this[i], v);    
    }

    return v;
}

answered Nov 3, 2009 at 18:21

answered Oct 3, 2020 at 15:10

I thought I’d share my simple and easy to understand solution.

For the min:

var arr = [3, 4, 12, 1, 0, 5];
var min = arr[0];
for (var k = 1; k < arr.length; k++) {
  if (arr[k] < min) {
    min = arr[k];
  }
}
console.log("Min is: " + min);

And for the max:

var arr = [3, 4, 12, 1, 0, 5];
var max = arr[0];
for (var k = 1; k < arr.length; k++) {
  if (arr[k] > max) {
    max = arr[k];
  }
}
console.log("Max is: " + max);

answered Oct 13, 2016 at 16:37

PeterPeter

5,0985 gold badges29 silver badges38 bronze badges

laktaklaktak

56.1k17 gold badges134 silver badges164 bronze badges

Aside using the math function max and min, another function to use is the built in function of sort(): here we go

const nums = [12, 67, 58, 30].sort((x, y) => 
x -  y)
let min_val = nums[0]
let max_val = nums[nums.length -1]

CyberknightCyberknight

1562 silver badges6 bronze badges

Iterate through, keeping track as you go.

var min = null;
var max = null;
for (var i = 0, len = arr.length; i < len; ++i)
{
    var elem = arr[i];
    if (min === null || min > elem) min = elem;
    if (max === null || max < elem) max = elem;
}
alert( "min = " + min + ", max = " + max );

This will leave min/max null if there are no elements in the array. Will set min and max in one pass if the array has any elements.

You could also extend Array with a range method using the above to allow reuse and improve on readability. See a working fiddle at http://jsfiddle.net/9C9fU/

Array.prototype.range = function() {

    var min = null,
        max = null,
        i, len;

    for (i = 0, len = this.length; i < len; ++i)
    {
        var elem = this[i];
        if (min === null || min > elem) min = elem;
        if (max === null || max < elem) max = elem;
    }

    return { min: min, max: max }
};

Used as

var arr = [3, 9, 22, -7, 44, 18, 7, 9, 15];

var range = arr.range();

console.log(range.min);
console.log(range.max);

answered Nov 3, 2009 at 18:23

answered Aug 26, 2014 at 16:57

The following code works for me :

var valueList = [10,4,17,9,3];
var maxValue = valueList.reduce(function(a, b) { return Math.max(a, b); });
var minValue = valueList.reduce(function(a, b) { return Math.min(a, b); });

let array = [0,20,45,85,41,5,7,85,90,111];

let maximum = array.sort((a, b) => b - a)[0];
let minimum = array.sort((a, b) => a - b)[0];

console.log(minimum, maximum)

Adam BelekoAdam Beleko

6287 silver badges14 bronze badges

answered Sep 23, 2014 at 7:48

answered Jan 9, 2014 at 18:46