c# - 我如何在 c# 中的特定字段值的结构数组上进行二进制搜索？

Question

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

Answer 1

您可以实现 IComparable<T>让你的结构在字段 (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<MyStruct> :

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

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

更新

如果你不想创建一个dummy 结构来进行比较，你可以实现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 };

更新:您可以同时支持 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);
    }
}