在排序后的 IList 中获取项目索引

我正在处理的代码的一部分是一个排序后的 List<someclass>。它根据类的属性（键）进行排序，我们需要访问该列表以：0) 检查它是否包含具有特定键的条目。1) 如果包含，检索或替换该项目。2) 如果不包含，在正确的位置添加该项目（以保持排序）。期望的方法是检索现有项目的索引或项目应该在的位置。List 的 IndexOf 方法不适合此用途，而且因为我们假设列表已排序，我们可以使用二分查找来优化搜索。以下是列表包含与键相同类型时的简单情况的实现

public static bool TryGetIndex<T>
(
  this System.Collections.Generic.IList<T> List
,
  T                                        Sought
,
  out int                                  Index
) where T : System.IComparable<T>
{
  bool result = false ;

  Index = 0 ;

  int lo = 0 ;
  int hi = List.Count - 1 ;

  while ( !result && ( lo <= hi ) )
  {
    Index = lo + ( hi - lo ) / 2 ;

    int diff = Sought.CompareTo ( List [ Index ] ) ;

    if (diff == 0 )
    {
      result = true ;
    }
    else if ( diff < 0 )
    {
      hi = Index - 1 ;
    }
    else
    {
      lo = ++Index ;
    }
  }

  return ( result ) ;
}

但是，这与我之前描述的情况不同，所以我有了这个版本

public delegate int Comparison<T,U> ( T Op1 , U Op2 ) ;

public static bool TryGetIndex<T,U>
(
  this System.Collections.Generic.IList<U> List
,
  T                                        Sought
,
  Comparison<T,U>                          Comparer
,
  out int                                  Index
)
{
  bool result = false ;

  Index = 0 ;

  int lo = 0 ;
  int hi = List.Count - 1 ;

  while ( !result && ( lo <= hi ) )
  {
    Index = lo + ( hi - lo ) / 2 ;

    int diff = Comparer ( Sought , List [ Index ] ) ;

    if ( diff == 0 )
    {
      result = true ;
    }
    else if ( diff < 0 )
    {
      hi = Index - 1 ;
    }
    else
    {
      lo = ++Index ;
    }
  }

  return ( result ) ;
}

这要求您提供一个执行比较的方法。这是一个示例，我尝试查找具有特定 Name 值的 DataRowView

delegate
(
  string                  Op1
,
  System.Data.DataRowView Op2
)
{
  return ( System.StringComparer.InvariantCultureIgnoreCase.Compare 
  ( 
    Op1 
  , 
    Op2 [ "Name" ]  
  ) ) ;
}

使用此代码查找现有项目的索引或不存在的项目所属的索引，允许您在正确的位置添加项目，以确保列表保持排序。并且二分查找比线性查找更有效，尤其是在列表变得很大时。