Get Array Max and Min between Start and End Indexes

Question

I need ideas for a simple, lightweight way to get the max and min values of an array of doubles. The trick is I only need the max and min between two indexes in the array.

The built-in arrayOfDoubles.Max() and arrayOfDoubles.Min() will not work, because they check the entire array.

This code will be running constantly and needs to be somewhat efficient. That said, simplicity and readability are more important than speed alone.

Here's one way to get the max and min between two indexes:

double[] array = new double[8] { 3, 1, 15, 5, 11, 9, 13, 7 };

int startIndex = 3;
int endIndex = 6;

// Get max and min between these two indexes in the array
double max = GetMax(array, startIndex, endIndex);
double min = GetMin(array, startIndex, endIndex);

Console.WriteLine("Max = " + max + ", Min = " + min);

Here is the code for GetMax, and GetMin would be very similar:

private static double GetMax(double[] array, int startIndex, int endIndex)
{
    double max = double.MinValue;

    for (int i = startIndex; i <= endIndex; i++)
    {
        // Increase max with each bigger value
        max = Math.Max(max, array[i]);
    }

    return max;
}

And the output: Max = 13, Min = 5

The Question: What other ways could I get the same result that might be simpler and wouldn't require too much overhead?

Answer 1

var list = array.Skip(startIndex).Take(endIndex - startIndex + 1).ToList();
var min = list.Min();
var max = list.Max();

Answer 2

You can do this by scanning the array once. This is the standard min/max tracking algorithm that is asked in a bazillion interview questions, so readability shouldn't be an issue.

void GetMinMax(double[] array, int start, int end, out double min, out double max)
{
    min = Double.MaxValue;
    max = Double.MinValue;

    // TODO: error checks for out-of-bounds, null, etc...
    for (int i = start; i <= end; ++i)
    {
        if (array[i] > max) max = array[i];
        if (array[i] < min) min = array[i];
    }
}

Edit:

Using Usman Zafar's answer to simplify and remove the need for several error checks:

void GetMinMax(IList<double> list, out double min, out double max)
{
    // TODO: null/empty check for list.

    min = Double.MaxValue;
    max = Double.MinValue;

    for (int i = 0; i < list.Count; ++i)
    {
        if (list[i] > max) max = list[i];
        if (list[i] < min) min = list[i];
    }
}

Now call with any IList<double>, or in your case: new ArraySegment<double>(array, 3, 4).

Answer 3

You can also do:

var segment = new ArraySegment<double>(array, startIndex, endIndex - startIndex + 1);
var min = segment.Min();
var max = segment.Max();

Answer 4

It should be obvious that finding the minimum and maximum elements in an unsorted array requires an O(n) algorithm because no matter how you do it you do have to examine each element, at least once. So the only optimizations you can hope for are implementation specific and can only bring you gains in terms of the constants.

There is however a clever trick you can employ for finding both minimum and maximum in the array using only 3*[n/2] comparisons. While this is not an asymptotic improvement, it is an improvement of n/2 compared to the typical 2*n comparison that are needed in the straight forward algorithm. So, if you expect to be performing lots of the min/max computations then it may be worth considering it as an option.

The way you do it is like this:

• maintain both minimum and maximum elements so far in two variables
• at each iteration:
  • compare the next two elements between each other to determine which one is larger
  • compare the larger element with the maximum (and swap if necessary)
  • compare the smaller element with the minimum (and swap if necessary)

You will be executing n/2 iterations of that loop, and 3 comparisons for each iteration for a total of 3*[n/2] operations.

Here's an implementation:

void GetMinMax(double[] array, int start, int end, out double min, out double max)
{
    min = array[start];
    max = array[start];

    if((end - start) % 2 == 0)               // if there's an odd number of elements
       start = start + 1;                    //   skip the first one

    for (int i = start + 1; i <= end; i += 2)
    {
        if(array[i] > array[i-1])
        {
            if(array[i] > max) max = array[i];
            if(array[i - 1] < min) min = array[i - 1];
        } else {
            if(array[i - 1] > max) max = array[i - 1];
            if(array[i] < min) min = array[i];
        }
    }
}

Answer 5

using the sweet drug that is LINQ:

        var res = array.Skip(startIndex).Take(1 + endIndex - startIndex );
        var min = res.Min();
        var max = res.Max();