Сравни алгоритмы поиска по идее, сложности и применению.

Алгоритмы поиска различаются идеей и сложностью: линейный (O(n)) — по любому массиву, бинарный (O(log n)) — по отсортированному, поиск по хеш-таблице (O(1)) — по ключу.

Линейный поиск

Проверяет элементы по очереди, пока не найдёт.

arr.indexOf(target); // O(n)

• Сложность: O(n).
• Плюсы: работает на любом (несортированном) массиве, прост.
• Применение: небольшие или неотсортированные данные.

Бинарный поиск

Делит отсортированный массив пополам на каждом шаге.

// O(log n), требует сортировки

• Сложность: O(log n).
• Плюсы: очень быстро на больших данных (1 млн → ~20 шагов).
• Минус: нужен отсортированный массив.

Поиск по хеш-таблице

Доступ по ключу через хеш.

map.get(key); // O(1) в среднем
set.has(x);   // O(1)

• Сложность: O(1) в среднем, O(n) в худшем (коллизии).
• Плюсы: мгновенный доступ по ключу.
• Минус: нужна структура (Map/Set/объект), доп. память.

Как выбирать

• Несортированные данные, разовый поиск → линейный.
• Отсортированный массив, много поисков → бинарный.
• Частые проверки наличия/доступ по ключу → хеш-таблица.

Коротко для собеседования

Линейный поиск — O(n), по любому массиву. Бинарный — O(log n), только по отсортированному (делит пополам). Хеш-таблица — O(1) в среднем, доступ по ключу. Выбор: несортированные разово — линейный, отсортированные многократно — бинарный, частый доступ по ключу — хеш.