自定義類型的二進制搜索數組

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?