我如何对 C# 中的特定字段值的结构数组进行二分搜索？

Question

我有一个结构数组，其中结构具有三个整数字段。它按其中一个字段（例如 F）排序，我想要一种对此字段进行二分搜索的方法，即，形式为 binarySearch(mystruct[] myarray, int val) 的函数，它返回索引其中字段 F = val 的结构的结构。我知道有一个现有的 Array.BinarySearch(T[] array, T value) 函数，但它只允许搜索与数组中的类型相同的类型 T 。这意味着如果我想搜索某个值，我需要创建一个新的结构并将字段 F 设置为该值，以便我可以将其传递给该函数。我不认为会有显着的性能开销，但它看起来很难看。我能想到的另一种方法是自己实现该功能，但是当存在如此类似的东西时，这也显得不优雅。有什么更好的方法或者首选哪种方法的建议吗？

Answer 1

您可以为您的结构实现 IComparable 以在字段 (F) 上进行比较，也可以为您的结构创建一个 IComparer<> 来进行比较将该字段传递给 Array.BinarySearch() 。

因此，

// using IComparable<T>
public struct MyStruct : IComparable<MyStruct>
{
    public int F { get; set; }

    // other fields that should not affect "search"
    public int X { get; set; }

    public int CompareTo(MyStruct other)
    {
        return F.CompareTo(other.F);
    }
}

可以这样调用：

MyStruct target = new MyStruct { F = 13 };

Array.BinarySearch(arrayOfMyStruct, target);

或者一个单独的 IComparer：

public struct MyStruct 
{
    public int F { get; set; }

    // other non-sort/search affecting properties
    public int X { get; set; }
}

public struct MyStructComparer : IComparer<MyStruct>
{
    public int Compare(MyStruct x, MyStruct y)
    {
        return x.F.CompareTo(y.F);
    }
}

可以这样调用：

MyStruct target { F = 13; }

Array.BinarySearch(myArrayOfStruct, target, new MyStructComparer());

第一个代码较少，但它将排序与类型强烈耦合，如果您想要根据情况改变排序（即允许多个排序顺序），这并不理想。后者提供了更大的灵活性，因为您可以提供独立于结构的多个不同的顺序，但它确实需要一个额外的类。

更新

如果您不想创建一个虚拟结构进行比较，您可以实现IComparable，如下所示：

public struct MyStruct : IComparable
{
    public int F { get; set; }

    // other non-sort/search affecting properties
    public int X { get; set; }

    public int CompareTo(object other)
    {
        // if the type is NOT an int, you can decide whether you'd prefer
        // to throw, but the concept of comparing the struct to something
        // unknown shouldn't return a value, should probably throw.
        return F.CompareTo((int)other);
    }
}

可以这样调用：

Array.BinarySearch(arrayOfMyStruct, 13);

但是同样，这将类的实现与给定的比较类型紧密联系在一起，我认为这比使用虚拟搜索目标更难看，但这是我个人的偏好。就我个人而言，特别是在初始化语法尽可能短的情况下，我更喜欢使用虚拟目标：

var target = new MyStruct { F = 13 };

UPDATE：您可以支持 int 和 MyStruct 比较，但它很快就会变得混乱，这就是为什么我个人再次建议使用虚拟结构来避免令人头痛的问题：

// implement IComparable<int> for the int search (w/o dummy), and IComparable<MyStruct> for sort
public struct MyStruct : IComparable, IComparable<MyStruct>, IComparable<int>
{
    public int F { get; set; }

    // other non-sort/search affecting properties
    public int X { get; set; }

    public int CompareTo(object other)
    {
        if (other is int) 
            return F.CompareTo((int)other);

        if (other is MyStruct)
            return F.CompareTo((MyStruct)other);

        throw new InvalidOperationException("Other must be int or MyStruct.");
    }

    public int CompareTo(MyStruct other)
    {
        return F.CompareTo(other.F);
    }

    public int CompareTo(int other)
    {
        return F.CompareTo(other);
    }
}

Answer 2

如果您的结构实现了 IComparable，您可以使用：

// myValue is an the value of the field to compare to
Array.BinarySearch(myArray, myValue);

如 http://msdn 中所述。 microsoft.com/en-us/library/y15ef976.aspx

您可以使用 IComparable 将结构与对象进行比较，以便您可以传入值而不是新值结构。在 CompareTo 的实现中，您可以将任何值与字段值进行比较，从而允许您说“我的结构应被视为大于/小于该数字”。

编辑：

这是您的结构的 CompareTo 示例：

public int CompareTo(object obj)
{
    if (obj is int)
    {
        return myIntField.CompareTo((int)obj);
    }
    return 0;
}

Answer 3

一种方法是创建一个自定义 IComparer，它仅根据该字段的值比较结构的实例，并将其传递给 BinarySearch 的此重载（您还需要创建一个“虚拟”结构实例来比较）。这可能是最纯粹的解决方案。

然而，实际上，您可以使用 LINQ 投影到字段值的集合中，并对其进行二分搜索；结果索引将与您搜索结构集合本身相同。例如：

var structs = new MyStruct[n];
var index = structs.Select(i => i.F).ToList().BinarySearch(42);

在上面的代码中，F 是字段的值，42 是您要搜索的值（其类型将是 F 的类型） ）。这不会那么快，但您不需要编写任何代码，并且速度很可能与您的情况无关。

更新：澄清一下：显然，由于投影操作，上面的代码将是 O(n)，因此在投影后使用二分搜索一次是愚蠢的（您可以简单地进行线性搜索）。但是，如果您打算进行多次搜索，那么它可能会开始有意义。

我绝对不建议在您的结构中覆盖 Equals ，除非实例之间的比较旨在减少到应用程序中各处比较 F 成员。