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

В теме Поиск и сортировка · Учебная карта
Главная мысль
Линейный поиск последовательно проверяет элементы до найденного совпадения или конца списка. Нужно заранее выбрать требуемый результат: первое совпадение, все позиции или только факт наличия. Для отсутствующего элемента используют явно согласованное значение, которое нельзя случайно принять за допустимый индекс.
Что происходит до первого совпадения
В списке 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, и явная проверка этого значения.
Можно ли остановиться после первого несовпадения?
В неупорядоченном списке нельзя: искомое значение может находиться дальше. Остановка допустима при найденном первом совпадении, если именно оно требуется.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему двоичный поиск требует упорядоченного массива
Как двоичный поиск использует сортировку, сужает полуинтервал кандидатов и отличает позицию вставки от фактического наличия искомого значения.
Открыть темуКак найти ошибку на границе цикла
Как находить ошибку на один шаг в цикле Python: включённое начало, исключённая правая граница range и допустимые индексы списка.
Открыть тему