Fast/efficient way to get index of minimum value in List<T>?

Question

Is there any way to find minimum value index more efficient/faster than this?

int minimumValueIndex = List.IndexOf(List.Min());

Answer 1

Microsoft seems don't want to rest, so they implemented another way to achieve the goal.

See MaxBy() in .NET 6.0.

It allows to find an item by max value of some key.

Answer 2

At present .NET supports value tuples which allows trivial solution:

var index = List.Select((item, index) => (item, index)).Max().index;

Answer 3

I'm lazy so I would use:

List.Sort();/* sorts the values least to greatest */
List[0];/* first item has the least value */

Answer 4

I improved @cdhowie's answer a little bit to make it more powerful. If there are more than one minimum elements, then this method will return the first one.

public static T GetMin<T, TOrder>(this IEnumerable<T> self, Func<T, TOrder> orderFunc, 
                                  out int minIndex, IComparer<TOrder> cmp = null)
{
    if (self == null) throw new ArgumentNullException("self");            

    IEnumerator<T> selfEnumerator = self.GetEnumerator();
    if (!selfEnumerator.MoveNext()) throw new ArgumentException("List is empty.", "self");

    if (cmp == null) cmp = Comparer<TOrder>.Default;

    T min = selfEnumerator.Current;
    minIndex = 0;
    int intCount = 1;
    while (selfEnumerator.MoveNext ())
    {
        if (cmp.Compare(orderFunc(selfEnumerator.Current), orderFunc(min)) < 0)
        {
            min = selfEnumerator.Current;
            minIndex = intCount;
        }
        intCount++;
    }

    return min;
}

Answer 5

If possible, keep track of the min value/index as the values are placed in to the list, so you do not need to loop through a full list. Then if new values are added to the list, check them against the min value that you saved, and change the new min value as necessary.

Of course that might not be suitable for your situation.

Answer 6

There's a problem with answer posted by @cdhowie in that it assumes that an IList<T> can efficiently access a particular item via its indexer. While that it true for arrays and List[T], it is in nono way guaranteed (take for an example, a singly-linked list that implements Ilist<T>).

If i was going to do this in a generic, Linqy way, I'd do something like:

public static IndexOfMinValue<T>( this IList<T> list ) where T:IComparable
{
  if ( list == null ) throw new ArgumentNullException("list") ;
  int? offset = null ;
  T    min    = default(T) ;

  int i = 0 ;
  foreach ( T item in list )
  {
    if ( !offset.HasValue || item.CompareTo(min) < 0 )
    {
       offset = i ;
       min    = item ;
    }
    ++i ;
  }

  if ( !offset.HasValue ) throw new ArgumentOutOfRangeException("list","list is empty") ;
  return offset.Value ;
}

Or, arguably cleaner, since we get rid of extraneous initialization and an extraneous compare in the body of the loop:

public static int IndexOfMin<T>( this IList<T> list ) where T:IComparable
{
  if ( list == null ) throw new ArgumentNullException("list") ;

  IEnumerator<T> enumerator  = list.GetEnumerator() ;
  bool           isEmptyList = ! enumerator.MoveNext() ;

  if ( isEmptyList ) throw new ArgumentOutOfRangeException("list","list is empty") ;

  int minOffset = 0 ;
  T   minValue  = enumerator.Current ;
  for ( int i = 1 ; enumerator.MoveNext() ; ++i )
  {
    if ( enumerator.Current.CompareTo(minValue) >= 0 ) continue ;
    minValue  = enumerator.Current ;
    minOffset = i ;
  }

  return minOffset ;
}

You could also use the stock Linq Aggregate() overload, though it's no cleaner or simpler than the brute force method (probably less efficient, too, IMHO):

IList<int> = GetSomeIntegers() ;

int minIndex = list.Aggregate( (Tuple<int,int,int>)null,
  ( acc , item ) => {
    int offset     = 0    ;
    int minValue   = item ;
    int minOffset  = 0    ;
    if ( acc != null )
    {
      offset    = acc.Item3 + 1 ;
      minValue  = item < acc.Item1 ? item   : acc.Item1 ;
      minOffset = item < acc.Item1 ? offset : acc.Item2 ;
    }
    return new Tuple<int, int, int>( minValue , minOffset , offset ) ;
  }).Item2 ;

Answer 7

In my own experience the LINQ aggregation methods such as Array.Max() and Array.Min() are typically slower than a manual for loop. So, you can consider something like this as an alternative approach:

int minima=0;
int mindex=0;

for(int i=0;i<List.Count;i++)
{
    if (List[i]<minima)
        {minima=List[i]; mindex=i;}
}

You can always test the speeds of both approaches on your environment by using System.Diagnostics.StopWatch.

Answer 8

Min Calculation: Finding the Min value in a collection cannot be done faster than O(n) so it may be no better way than that but just a different in the code style.

Finding Step: depending on your problem you may use some special data structure (such as binary tree, heap tree, ...) so you can find the index more faster.

Using something like min-heap tree you can get the min value with O(1) in expense of some special Add, Remove functions.

Answer 9

Yes, you can remove the overhead of List.IndexOf() by building a custom Min() extension. (Really, Enumerable.Min() should have an extension that selects the original element by key instead of selecting a transformation. This oversight is particularly painful in situations like this.)

public static int IndexOfMin(this IList<int> self)
{
    if (self == null) {
        throw new ArgumentNullException("self");
    }

    if (self.Count == 0) {
        throw new ArgumentException("List is empty.", "self");
    }

    int min = self[0];
    int minIndex = 0;

    for (int i = 1; i < self.Count; ++i) {
        if (self[i] < min) {
            min = self[i];
            minIndex = i;
        }
    }

    return minIndex;
}

Answer 10

Sure. Just write your own Min function, instead of using LINQ, that keeps track of the index of the current minimum value. By doing that you can avoid needing to find the index of the item based on it's min value.