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

Поиск

Под алгоритмами поиска понимается процесс просмотра списка в поисках некоторого конкретного элемента, называемого целевым. При последовательном поиске всегда предполагается, что список не отсортирован, поскольку некоторые алгоритмы на отсортированных списках показывают лучшую производительность. Обычно поиск производится не просто для проверки того, что нужный элемент в списке имеется, а и для того, чтобы получить данные, относящиеся к этому зна­чению ключа. Например, ключевое значение может быть номером сотрудника, порядковым номером или любым другим уникальным идентификатором. После того как нужный ключ найден, программа может, например, частично изменить связанные с ним данные или просто вывести всю запись. Во всяком случае, перед алгоритмом поиска стоит важная задача определения местонахождения ключа. Поэтому алгоритмы поиска возвращают индекс записи, содержащей нужный ключ. Если ключевое значение не найдено, то алгоритм поиска обычно возвращает зна­чение индекса, превышающее верхнюю границу массива. Положим, что элементы списка имеют номера от 1 до N. Это позволит возвращать 0 в случае, если целевой элемент отсутствует в списке. Для простоты предполагаем, что ключевые значения не повторяются.

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

Дата добавления: 2014-01-03