二进制搜索自定义类型的数组

我有一个对象数组A，每个对象都有公共字段Value（double），它在0和1之间有随机的双精度数.A按此字段排序。 我创建双随机= 0.25。 现在我想找到A中的第一个对象，其中包含A [index] .Value> = random。 我可以用某种方式使用int index = Array.BinarySearch（）吗？

Answer 1

这是您可以使用的BinarySearch的实现。 除了通常可以接受的其他参数之外，它还接受一个selector ，它确定应该为每个项目进行比较的实际对象，并且对于要查找它的值，它接受该类型的值，而不是该类型的值。arrays。

 public static int BinarySearch(this IList collection , TKey item, Func selector, Comparer comparer = null) { return BinarySearch(collection, item, selector, comparer, 0, collection.Count); } private static int BinarySearch(this IList collection , TKey item, Func selector, Comparer comparer , int startIndex, int endIndex) { comparer = comparer ?? Comparer.Default; while (true) { if (startIndex == endIndex) { return startIndex; } int testIndex = startIndex + ((endIndex - startIndex) / 2); int comparision = comparer.Compare(selector(collection[testIndex]), item); if (comparision > 0) { endIndex = testIndex; } else if (comparision == 0) { return testIndex; } else { startIndex = testIndex + 1; } } } 

使用它很简单：

 public class Foo { public double Value { get; set; } } private static void Main(string[] args) { Foo[] array = new Foo[5]; //populate array with values array.BinarySearch(.25, item => item.Value); } 

Answer 2

最好的方法就是自己动手。

 public static class ListExtensions { public static T BinarySearchFirst(this IList list, Func predicate) where T : IComparable { int min = 0; int max = list.Count; while (min < max) { int mid = (max + min) / 2; T midItem = list[mid]; int comp = predicate(midItem); if (comp < 0) { min = mid + 1; } else if (comp > 0) { max = mid - 1; } else { return midItem; } } if (min == max && predicate(list[min]) == 0) { return list[min]; } throw new InvalidOperationException("Item not found"); } } 

用法：

 var list = Enumerable.Range(1, 25).ToList(); var mid = list.Count / 2; //13 list.BinarySearchFirst(c => c >= 23 ? 0 : -1); // 23 

基于Can LINQ在订购集合时使用二进制搜索？