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

本文关键字：二进制 搜索 列表 | 更新日期: 2023-09-27 18:07:01

我正在使用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"的对象。

如何使用二分查找来解决这个问题?

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

首先，列表必须根据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());

返回的索引是:

如果找到item，则为排序列表中item的从零开始的索引;的位补数为负数如果没有，则下一个大于item或的元素的索引较大的元素，Count的按位补码。

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

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

虽然效率不高，但您仍然应该考虑这是否是一个更好的解决方案，因为它更容易实现，并且结果更容易处理。此外(这可能更重要)，即使列表没有在col1上排序，它也可以工作。

你可以这样写。

myList.Where(i => i.col1 == "abc").ToList();

使用字典，其中键存储在哈希表中。Linq可以很容易地创建cdictionary。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication41
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Limits> myList = new List<Limits>();
            //dictionary with unique keys
            Dictionary<string, Limits> dict1 = myList.AsEnumerable()
                .GroupBy(x => x.col2, y => y)
                .ToDictionary(x => x.Key, y => y.FirstOrDefault());
            //dictionary with keys having multiple values
            Dictionary<string, List<Limits>> dict2 = myList.AsEnumerable()
                .GroupBy(x => x.col2, y => y)
                .ToDictionary(x => x.Key, y => y.ToList());
            Limits abc = dict1["abc"];
        }
    }
    public class Limits
    {
        public String col1 { get; set; }
        public String col2 { get; set; }
        public String col3 { get; set; }
    }
}

除非您明确希望使用二进制搜索，否则您应该使用您可以使用的标准Linq函数。除非您的列表已经排序，否则这可能比二进制排序更有效。

  var myList = new List<Limits> {....}
  var entry = myList.Where(l => l.col1== "abc").FirstOrDefault();
  if(entry == null)
  { // no match found }

如果你真的想要二进制搜索，ref LINQ可以使用二进制搜索当集合是有序的吗?

相关文章：