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

Question

我正在使用 c# WPF 开发 Windows 应用程序。该应用程序需要 class 如下

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

你可以使用这样的东西。

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

Answer 2

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

返回的索引为：

The zero-based index of item in the sorted List, if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count.

您还可以使用 Where 方法获取具有属性:

的对象

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

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

排序，它也能正常工作

Answer 3

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

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

如果你真的想要二分查找，ref Can LINQ use binary search when the collection is ordered?

Answer 4

使用字典，其中键存储在散列中 table。 Linq 将轻松创建字典。

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; }
    }
}

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

Binary Search with List in c#

c#

algorithm

list

binary-search