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

Question

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

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

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

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

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

Answer 1

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

public static int BinarySearchForMatch<T>(this IList<T> list,
    Func<T,int> 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<TSource,TKey>(this IList<TSource> list, 
    Func<TSource,TKey> 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<TKey>.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<TSource,TKey>(this IList<TSource> list, 
    Func<TSource,TKey,int> 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<T>.BinarySearch与IComparer<T>.您不必编写自己的实现IComparer<T>- 我已经在MiscUtil中创建了一个IComparer<T>来自Comparison<T>委托的构建.这只能发现前三个条件,但二元搜索将从其余条件中找出最后一个条件.

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

public sealed class ComparisonComparer<T> : IComparer<T>
{
    readonly Comparison<T> comparison;

    public ComparisonComparer(Comparison<T> 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<Person>((p1, p2) => p1.ID.CompareTo(p2.ID));
int index = list.BinarySearch(employee, comparer);

MiscUtil也有ProjectionComparer你可能感兴趣的 - 你只需指定一个投影,就像OrderBy使用LINQ一样 - 但它实际上取决于你的用例.