使用委托条件对 C# 列表进行二分搜索

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

• 所需的项目必须位于左侧
• 所需的项目必须位于右侧
• 这是所需的物品
• 所需的内容不能在列表中

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

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

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

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