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

Ситуацию, описанную выше, назовем поиском в неструктурированном наборе. Разумный алгоритм для такого поиска остается один: последовательный перебор всех элементов множества до нахождения нужного. Ко­нечно, можно просматривать множество в случайном порядке (методом случайного перебора), но это может оказаться еще хуже, поскольку неиз­бежны повторные просмотры одних и тех же элементов, что только увели­чит время поиска.

Опишем алгоритм поиска методом последовательного перебора. Для описания алгоритма воспользуемся известным вам способом блок-схем (см рис.). В алгоритме учтем два возможных варианта результата: 1) искомые данные найдены; и 2) искомые данные не найдены. Результаты поиска нередко оказываются отрицательными, если в наборе нет искомых данных.

Символика блок-схем должна быть вам понятна. Из схемы видно, что если искомый элемент найден, то поиск может закончиться до окончания просмотра всего набора данных. Если же элемент не обнаружен, то поиск закончится только после просмотра всего набора данных.

Зададимся вопросом: какое среднее число просмотров приходится вы­полнять при использовании метода последовательного перебора? Есть два крайних частных случая:

-Искомый элемент оказался первым среди просматриваемых. Тогда просмотр всего один.

-Искомый элемент оказался последним в порядке перебора. Тогда число просмотров равно N, где N – размер набора данных. То же будет, когда элемент вообще не найден.