Best algorithm for determining the high and low in an array of numbers?

Question

I am using pseudo-code here, but this is in JavaScript. With the most efficient algorithm possible I am trying to find the high and low given an array of positive whole numbers. This is what I came up with, but I don't think it is probably best, and was just wondering if anyone has any other suggestions.

var low = 1;
var high = 1;
for ( loop numbers ) {
    if ( number > high ) {
        high = number;
    }
    if ( low == 1 ) {
        low = high;
    }
    if ( number < low ) {
        low = number;
    }
}

Answer 1

In python:

>>> seq = [1, 2, 3, 4, 5, 6, 7]
>>> max(seq)
7
>>> min(seq)
1

Answer 2

You have to do it in O(n) time because you need to loop through all (n) of the elements to check them because any one of the elements may be the min or max. (Unless they are already sorted.)

In other words you need to loop through all elements and do the max and min check like you have.

Sorting is usually at best O(n*log(n)). Thus it is slower than a single sweep through (O(n)).

Answer 3

Assuming the list isn't already sorted, that's about the best you can do. You can save yourself a comparison by doing the following (in pseudocode):

low = +INFINITY
high = -INFINITY
for each n in numbers:
    if n < low:
        low = n
    if n > high:
        high = n

This is an O(n) operation, which is basically the best you can do.

Answer 4

initialise the high and low to be the first element. makes a lot more sense than picking an arbitrarily "high" or "low" number.

var myArray = [...],
    low = myArray[0],
    high = myArray[0]
;
// start looping at index 1
for (var i = 1, l = myArray.length; i < l; ++i) {
    if (myArray[i] > high) {
        high = myArray[i];
    } else if (myArray[i] < low) {
        low = myArray[i];
    }
}

or, avoiding the need to lookup the array multiple times:

for (var i = 1, val; (val = myArray[i]) !== undefined; ++i) {
    if (val > high) {
        high = val;
    } else if (val < low) {
        low = val;
    }
}

Answer 5

Your example is pretty much the most efficient algorithm but obviously it won't work when all the numbers are less than 1 or greater than 1. This code will work in those cases:

var low = numbers[0]; // first number in array
var high = numbers[0]; // first number in array
for ( loop numbers ) {
    if ( number > high ) {
        high = number;
    }
    if ( number < low ) {
        low = number;
    }
}

Answer 6

If the list is small (where "small" is less than a few thousand elements) and you don't do it much (where "much" is less than a few thousand times) it doesn't matter. Profile your code first to find the real bottleneck before you worry about optimizing your max/min algorithms.

Now to answer the question you asked.

Because there is no way to avoid looking at every element of the list, a linear search is the most efficient algorithm. It takes N time, where N is the number of elements in the list. Doing it all in one loop is more efficient than calling max() then min() (which takes 2*N time). So your code is basically correct, though it fails to account for negative numbers. Here it is in Perl.

# Initialize max & min
my $max = $list[0];
my $min = $list[0];
for my $num (@list) {
     $max = $num if $num > $max;
     $min = $num if $num < $min;
}

Sorting and then grabbing the first and last element is the least efficient. It takes N * log(N) where N is the number of elements in the list.

The most efficient min/max algorithm is one where min/max is recalculated every time an element is added or taken away from the list. In effect, caching the result and avoiding a linear search each time. The time spent on this is then the number of times the list is changed. It takes, at most, M time, where M is the number of changes no matter how many times you call it.

To do that, you might consider a search tree which keeps its elements in order. Getting the min/max in that structure is O(1) or O(log[n]) depending what tree style you use.

Answer 7

The only further optimization I would suggest is optimizing the loop itself. It's faster to count down than to count up in JavaScript.

Answer 8

Although it's still an O(n) algorithm, you can do it 25% faster (that is, the proportionality constant is 3/2 vs 2) by comparing adjacent elements pairwise first, then comparing the smaller to min and the larger to max. I don't know javascript, but here it is in C++:

std::pair<int, int> minmax(int* a, int n)
{
  int low = std::numeric_limits<int>::max();
  int high = std::numeric_limits<int>::min();

  for (int i = 0; i < n-1; i += 2) {
    if (a[i] < a[i+i]) {
      if (a[i] < low) {
        low = a[i];
      }
      if (a[i+1] > high) {
        high = a[i+1];
      }
    }
    else {
      if (a[i] > high) {
        high = a[i];
      }
      if (a[i+1] < low) {
        low = a[i+1];
      }
    }
  }

  // Handle last element if we've got an odd array size
  if (a[n-1] < low) {
    low = a[n-1];
  }
  if (a[n-1] > high) {
    high = a[n-1];
  }

  return std::make_pair(low, high);
} 

Answer 9

var numbers = [1,2,5,9,16,4,6];

var maxNumber = Math.max.apply(null, numbers);
var minNumber = Math.min.apply(null, numbers);

Answer 10

nickf's algorithm is not the best way to do this. In the worst case, nickf's algorithm does 2 compares per number, for a total of 2n - 2.

We can do a fair bit better. When you compare two elements a and b, if a > b we know that a is not the min, and b is not the maximum. This way we use all of the available information to eliminate as many elements as we can. For simplicity, suppose we have an even number of elements.

Break them into pairs: (a1, a2), (a3, a4), etc.

Compare them, breaking them into a set of winners and losers - this takes n/2 compares, giving us two sets of size n/2. Now find the max of the winners, and the min of the losers.

From above, finding the min or the max of n elements takes n-1 compares. Thus the runtime is: n/2 (for the initial compares) + n/2 - 1 (max of the winners) + n/2 - 1 (min of the losers) = n/2 + n/2 + n/2 -2 = 3n/2 - 2. If n is odd, we have one more element in each of the sets, so the runtime will be 3n/2

In fact, we can prove that this is the fastest that this problem can be possibly be solved by any algorithm.

An example:

Suppose our array is 1, 5, 2, 3, 1, 8, 4 Divide into pairs: (1,5), (2,3) (1,8),(4,-). Compare. The winners are: (5, 3, 8, 4). The losers are (1, 2, 1, 4).

Scanning the winners gives 8. Scanning the losers gives 1.

Answer 11

Trying these snippets out for real on V8, Drew Hall's algorithm runs in 2/3 of the time of nickf's, as predicted. Making the loop count down instead of up cuts it to about 59% of the time (though that's more implementation-dependent). Only lightly tested:

var A = [ /* 100,000 random integers */];

function minmax() {
    var low = A[A.length-1];
    var high = A[A.length-1];
    var i, x, y;
    for (i = A.length - 3; 0 <= i; i -= 2) {
        y = A[i+1];
        x = A[i];
        if (x < y) {
            if (x < low) {
                low = x;
            }
            if (high < y) {
                high = y;
            }
        } else {
            if (y < low) {
                low = y;
            }
            if (high < x) {
                high = x;
            }
        }
    }
    if (i === -1) {
        x = A[0];
        if (high < x) {
            high = x;
        } else if (x < low) {
            low = x;
        }
    }
    return [low, high];
}

for (var i = 0; i < 1000; ++i) { minmax(); }

But man, it's pretty ugly.

Answer 12

Javascript arrays have a native sort function that accepts a function to use for the comparison. You can sort the numbers and just take the head and the tail to get the minimum and maximum.

var sorted = arrayOfNumbers.sort(function(a, b) { return a - b; }),
    ,min = sorted[0], max = sorted[sorted.length -1];

By default, the sort method sorts lexicographically (dictionary order) so that's why you have to pass in a function for it to use to get numerical sorting. The function you pass in needs to return 1, -1, or 0 to determine the sort order.

// standard sort function
function sorter(a, b) {
  if (/* some check */)
    return -1; // a should be left of b
  if (/*some other check*/)
    return 1; // a should be to the right of b
  return 0; // a is equal to b (no movement)
}

In the case of numbers, you can merely subtract the second from the first param to determine the order.

var numbers = [5,8,123,1,7,77,3.14,-5];

// default lexicographical sort
numbers.sort() // -5,1,123,3.14,5,7,77,8

// numerical sort
numbers.sort(function(a, b) { return a - b; }) // -5,1,123,3.14,5,7,77,8

Answer 13

this algorithm works for O(n) and no more extra memory needed to store elements...

enter code here
int l=0,h=1,index,i=3;
    if(a[l]>a[h])
                 swap(&a[l],&a[h]);
    for(i=2;i<9;i++)
    {
                                if(a[i]<a[l])
                                {
                                      swap(&a[i],&a[l]);  
                                }
                                if(a[i]>a[h])
                                {
                                             swap(&a[i],&a[h]);
                                }
    }
    printf("Low:  %d  High:  %d",a[0],a[1]);