How to get the Point with minimal X from an array of Points without using OrderBy?

Question

Imagine I have

 var points = new Point[]
 {
     new Point(1, 2),
     new Point(2, 3)
 };

To get the point with the minimum X I could:

 var result = points.OrderBy(point => point.X).First();

But for large arrays, I don't think this is the faster option. There is a faster alternative?

Answer 1

It is better to use

int x = points.Min(p => p.X);
var result = points.First(p => p.X == x);

as this eliminates the necessity of sorting this list (i.e., it is O(n) as opposed to, say, O(n log n)). Further, it's clearer than using OrderBy and First.

You could even write an extension method as follows:

static class IEnumerableExtensions {
    public static T SelectMin<T>(this IEnumerable<T> source, Func<T, int> selector) {
        if (source == null) {
            throw new ArgumentNullException("source");
        }

        int min = 0;
        T returnValue = default(T);
        bool flag = false;

        foreach (T t in source) {
            int value = selector(t);
            if (flag) {
                if (value < min) {
                    returnValue = t;
                    min = value;
                }
            }
            else {
                min = value;
                returnValue = t;
                flag = true;
            }
        }

        if (!flag) {
            throw new InvalidOperationException("source is empty");
        }

        return returnValue;
    }

Usage:

IEnumerable<Point> points;
Point minPoint = points.SelectMin(p => p.X);

You can generalize to your needs. The advantage of this is that it avoids potentially walking the list twice.

Answer 2

The following should be the quickest, but not the prettiest way to do it:

public static T MinValue<T>(this IEnumerable<T> e, Func<T, int> f)
{
    if (e == null) throw new ArgumentException();
    var en = e.GetEnumerator();
    if (!en.MoveNext()) throw new ArgumentException();
    int min = f(en.Current);
    T minValue = en.Current;
    int possible = int.MinValue;
    while (en.MoveNext())
    {
        possible = f(en.Current);
        if (min > possible)
        {
            min = possible;
            minValue = en.Current;
        }
    }
    return minValue;
}

I only included the int extension, but it is trivial to do others.

Edit: modified per Jason.