- Искомое
- Сравниваются
- Исключено
- Найдено
Линейный поиск
Линейный поиск — самый простой способ найти значение: начните с начала и проверяйте каждое значение по очереди, пока оно не найдётся. Он работает с любым списком, отсортированным или нет. Выберите искомое значение, запустите поиск или проходите его по одному сравнению и смотрите, как затраты зависят от того, где находится значение и есть ли оно вообще. Нажмите «Пуск», чтобы посмотреть поиск, или «Шаг» и «Назад», чтобы идти по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место. Пунктирная линия отмечает искомое значение. Выберите значение, число столбиков, начальный порядок или введите свои числа. Отключите «Остановиться на первом совпадении», чтобы найти все совпадения. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.
Как это работает
- Выберите искомое значение, число столбиков и начальный порядок. Или введите свои числа.
- Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы двигаться по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место поиска.
- Отключите «Остановиться на первом совпадении», чтобы проверить каждое значение и найти все совпадения.
Как работает линейный поиск
Сравните первое значение с искомым. Если они равны, поиск окончен. Если нет, переходите ко второму значению, затем к третьему и так далее. Если вы дошли до конца списка без совпадения, искомого значения в списке нет. Готовить ничего не нужно: список не обязан быть отсортированным.
Сколько сравнений
Значение на позиции k находится после k сравнений. В лучшем случае нужно одно сравнение, когда искомое значение стоит первым. В худшем — n, когда оно последнее или отсутствует, ведь только проверив каждое значение, можно быть уверенным, что его нет. В среднем для значения, которое есть в списке, нужно около (n + 1)/2. Для отсортированного списка двоичный поиск гораздо лучше: около log₂ n сравнений, 6 вместо максимум 40 для 40 значений.
Часто задаваемые вопросы
Как работает линейный поиск?
Он проверяет значения списка по одному, от первого до последнего, пока не найдёт искомое значение или пока значения не закончатся. Его также называют последовательным поиском.
Какова временная сложность линейного поиска?
O(n): в худшем случае, когда искомое значение последнее или отсутствует, оно сравнивается со всеми n значениями. В среднем для значения, которое есть в списке, нужно около (n + 1)/2 сравнений.
Когда линейный поиск — хороший выбор?
Для коротких списков, для неотсортированных списков, в которых ищут лишь раз или два, и для данных, которые можно читать только по порядку, например потока. Сортировать заранее, чтобы использовать двоичный поиск, имеет смысл, только если искать нужно много раз.
Почему отсутствующее значение обходится дороже всего?
Потому что ничто не подсказывает линейному поиску остановиться раньше. Исключить совпадение можно, только проверив каждое значение, поэтому значение, которого нет в списке, всегда требует n сравнений.
Мои числа куда-нибудь отправляются?
Нет. Поиск работает в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор