Информатика · объяснение и практика

Как линейный поиск обрабатывает найденный и отсутствующий элемент

Как линейный поиск проверяет элементы по порядку, возвращает первую подходящую позицию и обозначает отсутствие так, чтобы не спутать его с индексом ноль.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Поиск и сортировка · Учебная карта

Главная мысль

Линейный поиск последовательно проверяет элементы до найденного совпадения или конца списка. Нужно заранее выбрать требуемый результат: первое совпадение, все позиции или только факт наличия. Для отсутствующего элемента используют явно согласованное значение, которое нельзя случайно принять за допустимый индекс.

Что происходит до первого совпадения

В списке 8, 3, 8, 5 ищут число восемь. Если требуется первая позиция, совпадение находится сразу на индексе ноль при отсчёте с нуля. Можно остановиться: дальнейшая проверка не изменит первую найденную позицию. Если же требуются все совпадения, поиск продолжают и дополнительно получают индекс два. Одна и та же последовательность сравнений обслуживает разные вопросы при разных правилах остановки.

Для отсутствующей семёрки нужно проверить весь список. Ни одно раннее несовпадение не доказывает, что позже семёрки нет: элементы не упорядочены. Поэтому остановка после первого неудачного сравнения была бы логической ошибкой. Линейный поиск полезен именно тем, что не требует предварительной сортировки и сохраняет исходные позиции данных.

Как вернуть отсутствие без неоднозначности

В Python удобным результатом отсутствия может быть None, если найденный результат — обычный неотрицательный индекс. Тогда проверяют index is not None. Нельзя использовать просто if index: индекс ноль считается ложным при проверке истинности, хотя он обозначает допустимое первое совпадение. Факт наличия и числовая величина позиции — разные сведения.

Иногда учебный алгоритм возвращает минус один. Такое соглашение тоже возможно, но его надо обработать до обращения к списку. В Python индекс минус один сам по себе указывает на последний элемент, а не означает ошибку доступа. Если забыть условие отсутствия и сразу взять items[index], программа способна показать постороннее последнее значение вместо сообщения «не найдено».

Пример

Список [8, 3, 8, 5]: первая позиция 8 — индекс 0; все позиции — 0 и 2; для 7 совпадений нет.

Результат зависит от задачи поиска. Нулевой индекс является успехом, а не признаком отсутствия.

Какие случаи проверять в алгоритме

Пустой список должен корректно сообщать отсутствие без попытки читать первый элемент. Список из одного элемента позволяет отдельно проверить удачный и неудачный поиск. Затем полезны совпадение в начале, в конце и несколько повторов. Эти случаи проверяют остановку, границы и соглашение о результате лучше, чем один пример из середины длинного списка.

В худшем случае число сравнений пропорционально длине: при отсутствии придётся проверить все элементы. В лучшем непустом случае достаточно первого сравнения. Это оценка по количеству проверок, а не универсальное измерение времени любой программы. Сложное сравнение объектов или чтение данных с внешнего носителя добавляет собственные затраты, которых простая схема не описывает.

Если список заранее отсортирован и запросов много, может подойти двоичный поиск. Но сортировка тоже стоит работы и способна изменить исходные позиции. Поэтому замена линейного поиска другим методом требует учёта цели: нужен ли порядок оригинала, сколько запросов будет выполнено и доступно ли нужное правило сравнения. Сам по себе короткий список не требует сложной подготовки.

От чтения к действию

А теперь — вы

Поиск вернул индекс ноль. Что это означает при соглашении «None — не найдено»?

Частые вопросы

Почему индекс ноль нельзя считать неудачей?

Он обозначает первый элемент списка. Для отсутствия нужно отдельное соглашение, например None, и явная проверка этого значения.

Можно ли остановиться после первого несовпадения?

В неупорядоченном списке нельзя: искомое значение может находиться дальше. Остановка допустима при найденном первом совпадении, если именно оно требуется.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться