二进制搜索只匹配一个字段的自定义数据类型列表

本文关键字：字段 一个 列表 定义数据类型 搜索 二进制 | 更新日期: 2023-09-27 18:00:38

我有一个列表：

List<Student> allStudents = new List<Student>();

包含超过94000个Student对象，其中Student定义为：

public class Student
{
    public Int32 ID { get; set; }
    public String Surname { get; set; }
    public String Other_Names { get; set; }
    public String DOB { get; set; }
    // remaining fields omitted
}

并按姓氏排序。

从另一个来源获取Student对象后，我想在List allStudents中进行二进制搜索，以仅基于Surname属性找到匹配项。例如，如果"列出所有学生"中的现有记录为：

Student(8139241, "Flintstone", "Fred", "12/1/1967")

然后我搜索项目：

Student(7294311, "Flintstone", "Wilma", "14/6/1969")

二进制搜索应该是成功的。

列表。BinarySearch（T，IComparer）过载似乎是可能的，但它是一个可行的解决方案吗？或者有更好的策略吗？我将处理大量的记录和搜索，因此O（n）搜索功能将不可行。

提前感谢！

更新：我决定用Wintellect PowerCollections库中的MultiDictionary替换我的列表。此MultiDictionary可以接受重复的密钥。

二进制搜索只匹配一个字段的自定义数据类型列表

列表。BinarySearch是一个很好的解决方案，并且可以像您所期望的那样工作。这里有一个链接，显示了一个类似于IComparer所需的解决方案。不过，他们的示例没有使用Generic IComparer。

public class CompareCustomDataType : IComparer<Student> {
  public int Compare(Student x, Student y)
  {
    if (x == y)    return 0;
    if (x == null) return -1;
    if (y == null) return 1;
    return String.Compare(x.Surname, y.Surname);
  }
...
}

为Student类定义IComparable<T>接口。然后你的列表的所有排序和比较方法，包括BinarySearch()，你会自动使用这个方法。

有了这么多条目，您可能会更好地使用Dictionary<string, Student>查找，该查找将摊销为O（1）。虽然可能有多个学生有相同的姓氏，所以它可能有点像Dictionary<string, List<Student>>

同样正如Amit所指出的，当存在重复项目时使用二进制搜索可能很棘手，因为你不知道在一系列重复项目中会得到哪个索引。您必须搜索返回索引的左侧和右侧，以查看是否存在其他匹配的姓氏。

它有以下限制

  1. 如果List包含多个具有相同值的元素，则该方法只返回其中一个引用，并且可能返回其中任何一个引用（不一定是第一个）
  2. 列表必须已经根据比较器实现进行了排序；否则，结果不正确

我建议您使用Linq从您的列表中查找匹配数据。

  var data = students.where(o => o.SurName='xxxxx');

>您还可以使用谓词从List对象中使用Find或FindAll方法

相关文章：