Что хотят услышать интервьюеры:

Поиск за O(n) реализуется простым линейным проходом по коллекции: элемент проверяется последовательно, пока не найдётся совпадение. Такой подход подходит для неотсортированных данных или когда структура не поддерживает быстрый доступ по ключу. Важно понимать, что время зависит от размера коллекции, а не от сложности самого сравнения.

Определение:

O(n) — это линейная временная сложность, при которой число операций растёт пропорционально количеству элементов. Для поиска по ключу это обычно означает перебор всех элементов один за другим и сравнение ключа текущего элемента с искомым значением. Если совпадение найдено раньше, поиск завершается досрочно; в худшем случае просматривается вся коллекция.

Пример использования:

Если есть список объектов пользователей, и нужно найти пользователя по Id, но список не отсортирован и нет словаря, можно пройтись по нему циклом.

public class User
{
    public int Id { get; set; }
    public string Name { get; set; }
}

public static User? FindUserById(List<User> users, int id)
{
    foreach (var user in users)
    {
        if (user.Id == id)
            return user;
    }

    return null;
}

Пояснение кода:

Код нужен, потому что задача про реализацию поиска в C#.

Метод принимает список users и искомый id.
Цикл foreach последовательно перебирает каждый объект.
На каждой итерации сравнивается user.Id с нужным id.
Если совпадение найдено, метод сразу возвращает объект.
Если цикл завершился без совпадений, возвращается null.

Это и есть линейный поиск: в худшем случае будет проверено n элементов, где n — размер списка.

Ключевые моменты:

O(n) означает линейный перебор всех элементов.
Такой поиск часто используется для списков и массивов без индекса по ключу.
В лучшем случае элемент находится быстро, но в худшем нужно просмотреть всю коллекцию.
Если нужен частый поиск по ключу, обычно выгоднее использовать Dictionary<TKey, TValue>, где поиск быстрее.
Линейный поиск прост в реализации и не требует дополнительной структуры данных.

Каким образом реализовать поиск элемента по ключу с временной сложностью O(n)?