How to get a point with minimum X from an array of points without using OrderBy?

Question

Imagine what I have

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

To get a point with a minimum value of X, I could:

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

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

Answer 1

Better to use

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

since this eliminates the need to sort this list (i.e. O(n), unlike, say, O(n log n)). In addition, it is more clear than using OrderByand First.

You can 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;
    }

Using:

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

. , .

Answer 2

, :

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;
}

int, .

: Jason.

Answer 3

For those who want to do this today, MoreLinq is a library available by NuGet that includes an operator provided by other answers since several other useful operations are not present in the framework.