我有一个List< T>我想搜索不是给定项目,而是搜索满足给定条件的项目.给定列表中的项目,我可以测试4个条件中的哪一个为真：
>所需的项目必须在左侧
>所需的项目必须在右侧
>这是所需的项目
>所需的不能在列表中
快速浏览列表功能并不令人鼓舞,所以我想知道是否有人知道我可以使用的功能？
编辑：这是一个本地临时列表,所以我知道它将被正确排序
编辑：BinarySearch看起来几乎正确,但在我的情况下,我没有可比较的项目.我会使用Jon Skeet的解决方案并忽略一个arg,但我不确定我是否可以指望它始终是同一个arg.
解决方法
新编辑：我将在下面留下额外的二进制搜索,因为它们对其他人有用,这是最后一个选项,我想你真正想要的.如果要查找的项目“小于”指定的项目,则代理应返回正数,如果“大于”指定的项目,则返回负数,如果恰好,则返回0.
public static int BinarySearchForMatch<T>(this IList<T> list,Func<T,int> comparer)
{
int min = 0;
int max = list.Count-1;
while (min <= max)
{
int mid = (min + max) / 2;
int comparison = comparer(list[mid]);
if (comparison == 0)
{
return mid;
}
if (comparison < 0)
{
min = mid+1;
}
else
{
max = mid-1;
}
}
return ~min;
}
旧编辑：我将在下面留下原始答案,但这里有两个其他选项.
第一个是从源数据到密钥类型的投影,并指定要查找的密钥.比较本身只是以该键类型的默认方式完成：
public static int BinarySearchBy<TSource,TKey>(this IList<TSource> list,Func<TSource,TKey> projection,TKey key)
{
int min = 0;
int max = list.Count-1;
while (min <= max)
{
int mid = (min + max) / 2;
TKey midKey = projection(list[mid]);
int comparison = Comparer<TKey>.Default.Compare(midKey,key);
if (comparison == 0)
{
return mid;
}
if (comparison < 0)
{
min = mid+1;
}
else
{
max = mid-1;
}
}
return ~min;
}
第二个采用Func代替,将列表中的项目与我们正在寻找的密钥进行比较.当然,代码几乎完全相同 – 它只是改变的比较：
public static int BinarySearchBy<TSource,TKey,int> comparer,TKey key)
{
int min = 0;
int max = list.Count-1;
while (min <= max)
{
int mid = (min + max) / 2;
int comparison = comparer(list[mid],key);
if (comparison == 0)
{
return mid;
}
if (comparison < 0)
{
min = mid+1;
}
else
{
max = mid-1;
}
}
return ~min;
}
这些都是未经测试的,但至少要编译:)
原始答案：
您可以将List< T> .BinarySearch与IComparer< T>一起使用.您不必编写自己的IComparer实现< T> – 我已经在MiscUtil中建立了一个IComparer< T>来自比较< T>代表.这只能发现前三个条件,但二元搜索将从其余条件中找出最后一个条件.
事实上,代码是如此之短,我可能会把它贴在这里(无可否认,没有评论).
public sealed class ComparisonComparer<T> : IComparer<T>
{
readonly Comparison<T> comparison;
public ComparisonComparer(Comparison<T> comparison)
{
if (comparison == null)
{
throw new ArgumentNullException("comparison");
}
this.comparison = comparison;
}
public int Compare(T x,T y)
{
return comparison(x,y);
}
}
所以你可以这样做：
var comparer = new ComparisonComparer<Person>((p1,p2) => p1.ID.CompareTo(p2.ID)); int index = list.BinarySearch(employee,comparer);
MiscUtil还有一个您可能感兴趣的ProjectionComparer – 您只需指定一个投影,就像在带有LINQ的OrderBy中一样 – 但它实际上取决于您的用例.
