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

本文关键字：字段 结构 数组 二分搜索 | 更新日期: 2023-09-27 18:19:46

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

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

您可以为结构实现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());

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

更新

如果您不想创建要比较的虚拟结构，则可以实现如下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);
    }
}

如果你的结构实现了 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;
}

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

但是，实际上

，您可以使用 LINQ 投影到字段值集合中，然后进行二进制搜索;生成的索引将与搜索结构集合本身相同。例如：

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

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

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

我绝对不建议覆盖结构中的Equals，除非实例之间的比较旨在简化为比较应用程序中任何地方的F成员。

相关文章：