c#中使用列表进行二分搜索

Question

我正在使用 c# WPF 来开发 Windows 应用程序。应用程序需要一个类如下

public class Limits
{

    public String col1
    {
        get;
        set;
    }


    public String col2
    {
        get;
        set;
    }

    public String col3
    {
        get;
        set;
    }
}

我正在使用列表来存储对象，例如：-

List myList<Limits> = new List<Limits>();

“myList”有大约 15000 个对象。

现在，我想在此 myList 中搜索特定属性。例如：我想找出 col1 设置为“abc”的对象。

我如何使用二分搜索来解决这个问题？

Answer 1

首先，列表必须按col1属性排序，以便您能够使用二进制搜索。

您需要一个比较器来比较col1属性：

public class LimitsComparer : IComparer<Limits> {

  public int Compare(Limits x, Limits y) {
    return x.col1.CompareTo(y.col1);
  }

}

然后你可以用它来做二分查找：

int index = myList.BinarySearch(new Limits { col1 = "abc" }, new LimitsComparer());

返回的索引为：

已排序 List 中 item 的从零开始的索引（如果找到了 item）；否则，一个负数，它是下一个大于 item 的元素的索引的按位补码，或者，如果没有更大的元素，则为 Count 的按位补码。

您还可以使用该Where方法来获取具有该属性的对象：

List<Limits> result = myList.Where(x => x.col1 == "abc").ToList();

尽管这不是那么有效，但您仍然应该考虑这是否是更好的解决方案，因为它更容易实现并提供更易于处理的结果。此外（这可能更重要），即使列表未按col1.