Бинарный поиск Список пользовательских типов данных, соответствующих только одному полю

Question

У меня есть список:

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

, который содержит более 94 000 объектов ученика, где ученик определяется как:

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 из другого источника я хочу выполнить двоичный поиск по списку AllStudents, чтобы найти совпадение, основанное ТОЛЬКО на свойстве Surname.Например, если существующая запись в Списке allStudents равна:

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

и я ищу элемент:

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

, бинарный поиск должен быть успешным.

Перегрузка List.BinarySearch (T, IComparer) представляется возможной, но является ли это жизнеспособным решением?Или есть лучшая стратегия?Я буду иметь дело с большим количеством записей и поисков, поэтому функции поиска O (n) не будут жизнеспособными.

Заранее спасибо!

ОБНОВЛЕНИЕ: Я решил заменить свой Список наMultiDictionary из библиотеки Wintellect PowerCollections.Этот MultiDictionary может принимать дубликаты ключей.

Answer 1

List.BinarySearch - хорошее решение и работает так, как вы ожидаете.Вот ссылка, которая показывает решение, похожее на то, что вам нужно для IComparer.Однако в их примере не используется общий 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);
  }
...
}

Answer 2

Определите интерфейс IComparable<T> для вашего класса Student. Тогда все методы сортировки и сравнения в вашем списке, включая BinarySearch(), вы будете использовать автоматически.

Answer 3

Имеет следующее ограничение

1. Если список содержит более одного элемента с одинаковым значением, метод возвращает только одно из вхождений и может возвращать любое из вхождений, а необязательно первый.
2. Список должен быть уже отсортирован в соответствии с реализацией компаратора;в противном случае результат будет неправильным.

Я бы посоветовал вам использовать Linq, чтобы найти соответствующие данные из вашего списка.

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

> Вы также можете использовать методы Find или FindAll из объекта List, используя предикаты.

Answer 4

С таким количеством записей вам, вероятно, будет лучше использовать поиск Dictionary<string, Student>, который будет амортизироваться O (1). Хотя, возможно, может быть несколько учеников с одинаковой фамилией, это будет что-то вроде Dictionary<string, List<Student>>

Также, как указал Амит, использование бинарного поиска при наличии дублирующихся элементов может быть сложным, потому что вы не знаете, какой индекс вы получите в серии дубликатов. Вам придется искать слева и справа от возвращенного индекса, чтобы увидеть, существуют ли другие совпадающие фамилии.