Алгоритм последовательного поиска

Пусть имеется неупорядоченный массив записей с ключами К/, К2, ...,К_п. Необходимо найти запись с заданным ключом К [5J.

1. i = 1.
2. Если К = Ki, алгоритм заканчивается удачно.

3. Иначе i = i + 1.
4. Если i <= N, то вернуться к шагу 2. Иначе алгоритм заканчивается неудачно.

Условия окончания поиска следующие.

1. Элемент найден, то есть обнаружен ключ АГ, = К.
2. Все записи просмотрены, и совпадение не обнаружено.

Ясно, что максимальное число сравнений при удачном и неудачном поиске равно N.

Среднее число сравнений при удачном поиске равно (N + 1 )/2.

Для этого метода поиска как среднее, так и максимальное время поиска пропорционально п, то есть сложность рассмотренного алгоритма равна О(п).

Оптимальный последовательный поиск

Приведенный выше алгоритм при всей своей очевидности не является, однако оптимальным. В алгоритме последовательного поиска в цикле имеются две проверки: на совпадение ключей и на выход значения индекса за пределы массива.

Если гарантировать, что ключ всегда будет найден, то без второго условия можно обойтись. Для этого достаточно в конце массива поместить дополнительный элемент, присвоив ему значение искомого ключа К. Назовем такой вспомогательный элемент «барьером», так как он предотвращает выход за пределы массива [3].

Алгоритм оптимального последовательного поиска

Пусть имеется неупорядоченный массив записей с ключами К], К2, Необходимо найти запись с заданным ключом К.

1 .к_п+1 = к
2. i = 1.
3. Если К = Kj, на шаг 5.
4. Иначе i = i + 1. На шаг 3.
5. Если / = N+1, то поиск неудачен (ключ найден в барьере), иначе - поиск удачен (ключ найден в /-ом элементе массива).

Таким образом, ключ всегда будет найден в записи с индексом /.

При / = N+1 (индекс достиг конца массива) ключ не найден (то есть найден только в барьере). Поиск неудачен. В противном случае - поиск удачен.

Такой подход позволяет исключить в среднем (N + 1)/2 сравнений.

Алгоритм, реализующий описанный выше метод поиска, называется алгоритмом оптимального последовательного поиска.

Сложность рассмотренного алгоритма также равна О(п).

Если известно, что ключи упорядочены (например, расположены в возрастающем порядке), то алгоритм последовательного поиска целесообразно несколько изменить.

Пусть имеется множество записей с ключами К, К2, причем К) < К2

<..<К_п. Необходимо найти запись с заданным ключом К. В целях увеличения скорости работы в конец массива помещается дополнительный элемент — «барьер», значение которого должно быть больше значения искомого ключа К (например, К+1).

В отличие от поиска в неупорядоченном массиве просмотр элементов упорядоченного массива заканчивается в тот момент, когда первый раз выполнится условие К < Kj. Очевидно, что все элементы Kj+i, К„ будут больше К [6].

Если К = К/ - поиск удачен. В противном случае, искомого элемента нет в массиве.

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

Пусть имеется упорядоченный массив записей с ключами К/, К2, Необходимо найти запись с заданным ключом К.

1 .К_п+1 = К+1
2. i = 1.
3. Если К <= K_it на шаг 5.
4. Иначе i = i + 7, на шаг 3.
5. Если К = Kj, то поиск удачен, иначе - поиск неудачен.

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

Таким образом, среднее число сравнений и при удачном, и при неудачном поиске равно (N+l)/2, следовательно, сложность рассмотренного алгоритма также равна О(п).