5.1. Линейный поиск
Содержание
Линейный, или последовательный, поиск - это проверка элементов массива один за другим в порядке их расположения. Так можно выяснить, существует ли заданное значение, найти индекс совпадающего элемента либо обнаружить все элементы, отвечающие условию. При отсутствии дополнительных сведений об упорядоченности данных последовательный просмотр служит простым способом поиска.
Что нужно понять
- Поиск может отвечать на вопрос о наличии хотя бы одного подходящего элемента.
- Если требуется местоположение, результатом становится индекс найденного элемента.
- Для поиска всех совпадений определяют их количество и при необходимости индексы.
- Проверять можно не только равенство заданному числу, но и выполнение другого условия.
- Линейный поиск организуют последовательным просмотром элементов по порядку записи.
- В отличие от поиска в упорядоченном наборе, такой алгоритм не требует заранее отсортированных данных.
- Если подходящих элементов нет, алгоритм должен предусматривать соответствующий результат.
Видео
5:40
Скачать к теме
Главное по теме
Линейный поиск последовательно сравнивает элементы массива с искомым значением или условием.
Ключевые понятия
Как это работает
Что нужно запомнить
- Отличайте проверку наличия, поиск индекса и поиск всех совпадений.
- Условие можно сформулировать как равенство или проверку свойства элемента.
Проверь себя
Что называют линейным поиском?
Какой результат нужен для задачи поиска одного значения по месту?
Что можно искать вместо элемента, равного заданному x?
Что требуется для получения всех совпадений?
Для каких массивов можно применить простой последовательный просмотр?