使用委托条件对 C# 列表进行二分搜索
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/504645/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Binary search of a C# list using delegate condition
提问by BCS
I have a List<T>that I want to search not for a given item but for an item satisfying a given condition. Given an item in the list I can test which of 4 conditions is true:
我有一个List<T>我想搜索的不是给定的项目，而是满足给定条件的项目。给定列表中的一项，我可以测试 4 个条件中的哪一个为真：
- the desired item must be to the left
- the desired item must be to the right
- this is the desired item
- the desired can't be in the list
- 所需的项目必须在左侧
- 所需的项目必须在右侧
- 这是所需的项目
- 所需的不能在列表中
A quick glance at the list functions was not encouraging so I'm wondering if anyone knows off a function I can use?
快速浏览一下列表函数并不令人鼓舞，所以我想知道是否有人知道我可以使用的函数？
Edit: this is a local temp list so I known that it will be sorted correctly
编辑：这是一个本地临时列表，所以我知道它会被正确排序
Edit: BinarySearch looks almost right but in my case I don't have an item to compare with. I'd use Jon Skeet's solution and ignore one arg, but I'm not sure that I can count on it always being the same arg.
编辑： BinarySearch 看起来几乎正确，但在我的情况下，我没有可以比较的项目。我会使用 Jon Skeet 的解决方案并忽略一个 arg，但我不确定我是否可以指望它总是相同的 arg。
采纳答案by Jon Skeet
New edit:I'll leave the extra binary searches below, as they'll be useful for others, and here's a final option which is I think what you actually want. Your delegate should return a positive number if the item it's looking for is "less than" the one specified, a negative number if it's "greater than" the one specified, and 0 if it's just right.
新编辑：我将在下面留下额外的二进制搜索，因为它们对其他人有用，这是我认为您真正想要的最后一个选项。如果它要查找的项目“小于”指定的项目，则您的委托应返回一个正数，如果它“大于”指定的项目，则返回一个负数，如果它恰到好处，则返回 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;
}
Old edit:I'll leave the original answer below, but here are two other options.
旧编辑：我将在下面留下原始答案，但这里有另外两个选项。
The first takes a projection from the source data to a key type, and specifies the key to find. The comparison itself is just done in the default way for that key type:
第一个将源数据投影到键类型，并指定要查找的键。比较本身只是以该键类型的默认方式完成的：
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;
}
The second takes a Func instead, to compare an item from the list with the key we're looking for. The code is almost exactly the same, of course - it's just the comparison which changes:
第二个使用 Func 代替，将列表中的项目与我们正在寻找的键进行比较。当然，代码几乎完全相同 - 只是比较发生了变化：
public static int BinarySearchBy<TSource,TKey>(this IList<TSource> list,
Func<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;
}
These are both untested, but do at least compile :)
这些都未经测试，但至少可以编译:)
Original answer:
原答案：
You can use List<T>.BinarySearchwith an IComparer<T>. You don't have to write your own implementation of IComparer<T>- I've got on in MiscUtilwhich builds an IComparer<T>from a Comparison<T>delegate. That only spots the first three conditions, but the binary search will work out the last one from the rest.
您可以List<T>.BinarySearch与IComparer<T>. 您不必编写自己的实现IComparer<T>- 我已经在MiscUtil 中进行了，它IComparer<T>从一个Comparison<T>委托中构建了一个。这只会发现前三个条件，但二分搜索将从其余条件中找出最后一个。
In fact, the code is so short I might as well paste it here (sans comments, admittedly).
事实上，代码太短了，我不妨把它贴在这里（无可否认，没有评论）。
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);
}
}
So you might do something like:
因此，您可能会执行以下操作：
var comparer = new ComparisonComparer<Person>((p1, p2) => p1.ID.CompareTo(p2.ID));
int index = list.BinarySearch(employee, comparer);
MiscUtil also has a ProjectionCompareryou might be interested in - you just specify a projection, just like in OrderBywith LINQ - but it really depends on your use case.
MiscUtil 也有一个ProjectionComparer您可能感兴趣的 - 您只需指定一个投影，就像在OrderByLINQ 中一样 - 但它实际上取决于您的用例。
回答by Joel Coehoorn
Are you sure of those conditions? Normally that works if the list is sorted, in which case perhaps you want to use a SortedList<TKey, TValue>in the first place.
你确定这些条件？通常情况下，如果列表已排序，则可以使用，在这种情况下，您可能首先想使用 a SortedList<TKey, TValue>。
Either way, assuming C# 3.0 or later you probably want the .Where()method. Write in your condition as a Lambda and let the framework do the search. It should use a search technique appropriate to the collection.
无论哪种方式，假设 C# 3.0 或更高版本，您可能需要该.Where()方法。将您的条件写为 Lambda，让框架进行搜索。它应该使用适合集合的搜索技术。
回答by Saulius ?emaitaitis
You might want to implement it in a custom comparator for your object (strangely called comparer in C# docs).
您可能希望在对象的自定义比较器中实现它（在 C# 文档中奇怪地称为比较器）。
