使用委托条件二进制搜索C#列表

我有一个List ,我想搜索不是给定项目,而是搜索满足给定条件的项目。 给定列表中的项目,我可以测试4个条件中的哪一个为真:

  • 所需的项目必须在左侧
  • 所需的项目必须在右侧
  • 这是所需的项目
  • 所需的不能在列表中

快速浏览列表function并不令人鼓舞,所以我想知道是否有人知道我可以使用的function?

编辑:这是一个本地临时列表,所以我知道它将被正确排序

编辑:BinarySearch看起来几乎正确,但在我的情况下,我没有可比较的项目。 我会使用Jon Skeet的解决方案并忽略一个arg,但我不确定我是否可以指望它始终是同一个arg。

新编辑:我将在下面留下额外的二进制搜索,因为它们对其他人有用,这是最后一个选项,我想你真正想要的。 如果要查找的项目“小于”指定的项目,则代理应返回正数,如果“大于”指定项目,则返回负数,如果恰好,则返回0。

 public static int BinarySearchForMatch(this IList list, Func 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(this IList list, Func 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.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(this IList list, Func 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.BinarySearchIComparer 。 您不必编写自己的IComparer - 我已经在MiscUtil中使用它从Comparison委托构建IComparer 。 这只能发现前三个条件,但二进制搜索将找出其余条件中的最后一个。

事实上,代码是如此之短,我可能会把它贴在这里(无可否认,没有评论)。

 public sealed class ComparisonComparer : IComparer { readonly Comparison comparison; public ComparisonComparer(Comparison 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((p1, p2) => p1.ID.CompareTo(p2.ID)); int index = list.BinarySearch(employee, comparer); 

MiscUtil还有一个您可能感兴趣的ProjectionComparer - 您只需指定一个投影,就像在带有LINQ的OrderBy一样 - 但它实际上取决于您的用例。

你确定那些条件吗? 通常,如果列表已排序,则可以正常工作,在这种情况下,您可能希望首先使用SortedList

无论哪种方式,假设C#3.0或更高版本,您可能需要.Where()方法。 在您的条件下写为Lambda并让框架进行搜索。 它应该使用适合该集合的搜索技术。

您可能希望在对象的自定义比较器中实现它(在C#docs中奇怪地称为比较器)。