c# - 使用委托(delegate)条件对 C# 列表进行二进制搜索

Question

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

• 所需的项目必须在左侧
• 所需的项目必须在右边
• 这是想要的元素
• 所需的不能在列表中

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

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

编辑:BinarySearch 看起来几乎正确，但就我而言，我没有可比较的项目。我会使用 Jon Skeet 的解决方案并忽略一个 arg，但我不确定我是否可以指望它始终是相同的 arg。

Answer 1

新编辑:我将在下面保留额外的二进制搜索，因为它们对其他人有用，这是最后一个选项，我认为这是您真正想要的。如果它要查找的项“小于”指定的项，则您的委托(delegate)应返回一个正数；如果它“大于”指定的项，则返回一个负数；如果恰好，则返回 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 - 但这实际上取决于您的用例。