Линейный поиск
Линейный поиск — это способ найти нужное значение в последовательности, проверяя её элементы один за другим, начиная с первого. Поиск заканчивается, когда значение найдено или проверены все элементы.
Линейный поиск часто строят с помощью циклического алгоритма: на каждой итерации сравнивают очередной элемент с искомым значением. Если элементы не упорядочены, такой способ подходит в общем случае. Он является частью построения алгоритма, когда требуется организовать перебор данных.
Как работает поиск
- Выбрать первый элемент последовательности.
- Сравнить его с искомым значением.
- Если значения равны, завершить поиск и запомнить позицию.
- Если значения различаются, перейти к следующему элементу.
- Если достигнут конец последовательности, сообщить, что значение не найдено.
В худшем случае приходится проверить все \(n\) элементов, поэтому время работы линейного поиска имеет порядок \(O(n)\). В лучшем случае искомое значение находится первым, и достаточно одной проверки. Дополнительная память обычно имеет порядок \(O(1)\): кроме нескольких переменных, ничего сохранять не требуется.
Пусть массив равен \([7, 3, 9, 4]\), а искомое значение — \(9\). Сравнения выполняются так: \(7 \ne 9\), затем \(3 \ne 9\), затем \(9=9\). Значение найдено на третьей позиции, если считать позиции с единицы, или с индексом \(2\), если индексация начинается с нуля.
Линейный поиск не требует, чтобы массив был упорядочен. Двоичный поиск работает быстрее на больших данных, но применим только тогда, когда последовательность отсортирована и можно каждый раз отбрасывать половину области поиска.
Сколько элементов нужно проверить в худшем случае при линейном поиске в массиве из 12 элементов?
Главное
- Линейный поиск последовательно сравнивает искомое значение с элементами от начала к концу.
- В худшем случае проверяются все элементы, поэтому сложность равна \(O(n)\).
- Метод не требует сортировки; для отсортированных данных иногда используют двоичный поиск.