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

Question

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

Answer 1

这里是BinarySearch，您可以使用一个实现。除了通常会被接受的其他参数之外，它还接受selector，它确定每个项目应该比较的实际对象，并且找到它的值接受该类型的值，而不是阵列。

public static int BinarySearch<TSource, TKey>(this IList<TSource> collection 
    , TKey item, Func<TSource, TKey> selector, Comparer<TKey> comparer = null) 
{ 
    return BinarySearch(collection, item, selector, comparer, 0, collection.Count); 
} 
private static int BinarySearch<TSource, TKey>(this IList<TSource> collection 
    , TKey item, Func<TSource, TKey> selector, Comparer<TKey> comparer 
    , int startIndex, int endIndex) 
{ 
    comparer = comparer ?? Comparer<TKey>.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<T>(this IList<T> list, Func<T, int> predicate) 
      where T : IComparable<T> 
    { 
     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 use binary search when the collection is ordered?