Алгоритм. Алгоритмы поиска (поиск в массиве: линейный, с барьером

Алгоритмы поиска (поиск в массиве: линейный, с барьером, бинарный поиск в упорядоченном массиве, поиск минимума, максимума в массиве).

Линейный поиск в массиве

Постановка задачи

Пусть дан массив элементов A и ключ b. Необходимо выяснить, имеется ли в массиве A элемент, совпадающий по значению с ключом b.

Алгоритм

Линейный поиск подразумевает последовательный просмотр всех элементов массива А в порядке их расположения, пока не найдется элемент равный b. Если заранее неизвестно, имеется данный элемент в массиве или нет, то необходимо следить за тем, чтобы поиск не вышел за границы массива, что можно реализовать без использования и с использованием барьерного элемента.

Алгоритм без использования барьерного элемента

1. Установить I = 1
2. Если A[I] = b, элемент найден (алгоритм закончен удачно), перейти к шагу 5
3. Увеличить I на 1
4. Если I £ N, то перейти к шагу 2. В противном случае алгоритм окончен неудачно.
5. Конец

Алгоритм с использованием барьерного элемента. Искомый элемент b помещаем в массив на (N+1)-е место, таким образом этот элемент всегда в массиве будет найден, вопрос только в том, на каком месте мы его нашли. Если нашли на (N+1)-м месте, то это означает, что такого элемента в массиве нет, иначе его номер в массиве меньше или равен N.

Алгоритм поиска с барьером

1. Установить I = 1
2. Если A[I] = b, элемент найден, перейти к шагу 5
3. Увеличить I на 1
4. Перейти к шагу 2
5. Если I £ N, то элемент в массиве есть, иначе элемента в массиве нет.
6. Конец

Сложность алгоритма поиска естественно оценивать по числу сравнений элементов массива с искомым элементом.

Следует отметить, что в общем случае при линейном поиске среди N элементов требуется в среднем N сравнений в случае успешного поиска и 2*N сравнений в наихудшем случае.
При линейном поиске с барьером среди N элементов требуется в среднем N/2 сравнений в случае успешного поиска и N сравнений в наихудшем случае.
Затраты времени для больших массивов в обоих случаях велики. Применяется алгоритм линейного поиска (с барьером или без), если никакой дополнительной информации о данных массива нет.

Дата добавления: 2015-07-12