Поиск записи в списке без сканирования всех записей

Question

У меня есть список записей (структура), подобный этому:

struct Rec
{
     int WordID;
     int NextID;
     int PrevID;
}

List<Rec>= New List<Rec>(){...};

Мне нужен способ найти значение типа «Rec» в списке без поиска всех записей, таких как бинарный поиск.Я хочу, чтобы сложность по времени была меньше O (n)

Answer 1

Лучший способ поиска элемента в списке, конечно, не иметь список, но иметь хеш-таблицу.

Если у вас есть словарь вместо списка (или словарь И список), вы можете выполнить поиск точных значений в усредненном \ амортизированном O (1).

Вы также можете использовать бинарный поиск, но только если список отсортирован, есть метод List<T>.BinarySearch и поиск будет O (log n).

Сортировка списка с n элементами - O (n log n). Вставка n элементов в хеш-таблицу вместо этого усредняется O (n), вставка элемента - усреднение O (1). Это означает, что создание хеш-таблицы (или ее синхронизация со списком) будет быстрее, чем сортировка списка. Однако учтите, что хеш-таблица потребляет больше памяти, потому что она должна хранить внутри себя массив сегментов.

Answer 2

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