Какова сложность поиска элемента в списке в C#?

Сложность поиска зависит от конкретного типа списка и используемого метода.

1. List<T>:

• Contains() или IndexOf(): Линейный поиск (O(n)).
• BinarySearch(): Двоичный поиск (O(log n)), но требует, чтобы коллекция была предварительно отсортирована.

2. LinkedList<T>:

• Поддерживает только последовательный обход (O(n)). Отсутствие индексатора делает поиск медленнее, чем в List<T> для большинства случаев.

Практический выбор:

• Для частых операций поиска по уникальному ключу используйте HashSet<T> (O(1) в среднем) или Dictionary<TKey, TValue>.
• Если данные отсортированы и редко меняются, List<T>.BinarySearch() — оптимальный выбор.

Пример кода:

// Линейный поиск в List<T> (O(n))
List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
bool exists = numbers.Contains(3); // true

// Бинарный поиск в отсортированном List<T> (O(log n))
numbers.Sort();
int index = numbers.BinarySearch(3); // возвращает индекс 2

// Поиск в HashSet<T> (O(1) в среднем)
HashSet<int> numberSet = new HashSet<int> { 1, 2, 3, 4, 5 };
bool fastExists = numberSet.Contains(3); // true, выполняется очень быстро