自定义类型的二进制搜索阵列 [英] Binary searching array of custom type

问题描述

我有对象的数组A，每个公共字段值（双），其中有随机双打0与1之间A是由该字段排序。我创建双随机= 0.25。现在，我想找到从A的第一个对象与A [索引] .value的> =随机的。我能做到这一点，在某种程度上INT指数= Array.BinarySearch（）？

I have an array A of objects, each with the public field Value (double) which have random doubles between 0 and 1. A is sorted by this field. I create double random = 0.25. Now I want to find the first object from A with A[index].Value >= random. Can I do this with int index = Array.BinarySearch() in some way?

推荐答案

下面是二分查找的实现，您可以使用。此外，通常会接受其他参数，还接受选择这就决定了要对每个项目进行比较实际的目标，并为价值发现接受该类型的一个值，而不是在阵列的类型。

Here is an implementation of BinarySearch that you can use. In addition to the other arguments that would normally be accepted, it also accepts a selector which determines the actual object that should be compared for each item, and for the value to find it accepts a value of that type, rather than the type of the array.

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);
}

这篇关于自定义类型的二进制搜索阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！