Последовательный поиск в неупорядоченном массиве

Алгоритмы поиска

Очень часто в реальной жизни нам приходится сталкиваться с задачей поиска информации в объеме данных. Например, поиск фамилии ученика в журнале, поиск нужного слова в словаре. Существует множество алгоритмов поиска, но из всего многообразия алгоритмов мы рассмотрим два основных и наиболее часто используемых.

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

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

Для оценки алгоритмов мы будем использовать такую характеристику, как сложность.

Последовательный поиск в неупорядоченном массиве

Пример 31
Человек ищет на полке книжку с определенным названием. Книги на полке стоят вразнобой, то есть не по алфавиту. Как будет действовать человек? Он будет сравнивать по порядку название каждой книги на полке с тем названием, которое ему нужно найти. В итоге он или найдет нужную ему книгу, или, просмотрев все книги на полке, не обнаружит нужной книги. Этот пример передает суть алгоритма последовательного поиска в неупорядоченном массиве. Приведем его формальную запись.
Алгоритм последовательного поиска в неупорядоченном массиве
Имеется массив a[1 … n], требуется найти элемент массива, равный P:

1. Установить i = 1.

2. Если a_i = P, алгоритм завершил работу успешно.

3. Увеличить i на 1.

4. Если i ≤ n, то перейти к шагу 2. В противном случае алгоритм завершил работу безуспешно.

Оценим сложность алгоритма последовательного поиска. Естественно оценивать сложность по числу сравнений с искомым элементом. В худшем случае искомый элемент окажется на последнем месте или не будет найден, и тогда необходимо будет проделать n сравнений, то есть сложность алгоритма будет равна n. Такой поиск также называют линейным, так как он решает задачу поиска с линейной скоростью по количеству сравнений.

Скачать текст программы