Поиск

Алгоритмические и математические аспекты поиска достаточно сложны и их исследованию посвящены многочисленные работы. Наиболее полно эти вопросы рассматриваются в ранее упоминавшейся трилогии Д. Кнута. Мы же ограничимся самыми простыми алгоритмами и программами, позволяющими понять суть проблемы и познакомиться с некоторыми подходами к повышению эффективности поиска.

В достаточно общих чертах задача поиска формулируется следующим образом. Имеется массив а, содержащий п однородных объектов (чисел, строк, записей), и нужно установить, содержится ли в нем заданный объект q. При положительном ответе следует дополнительно сообщить порядковый номер (индекс) j найденного объекта (a[j] = q).

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

Если исходный массив а не упорядочен, то единственно разумным способом является последовательный перебор всех элементов массива и сравнение их с заданным значением. В лучшем случае мы можем получить ответ на первом же шаге, если q = а [ 1 ]. В худшем случае придется перебрать все п элементов и только после этого дать положительный или отрицательный ответ. В среднем количество проверок может оказаться порядка п/2.

Классический алгоритм последовательного поиска включает следующие шаги:

S1 Остановить начальный индекс равным 1 (j = 1).

S2:Проверить условие q = a[j]. Если оно выполняется, то сообщить, что искомое значение находится в массиве а на j-ом месте и прервать работу. В противном случае продолжить работу.

S3:Увеличить индекс j на 1.

S4:Проверить условие j < n + 1. Если оно выполняется, то вернуться к шагу S2. В противном случае сообщить, что значение q в массиве а не содержится.

Большинству программистов кажется, что приведенный алгоритм является оптимальным и ничего сократить в нем нельзя. Однако это — очень распространенное заблуждение. Д. Кнут приводит модификацию алгоритма последовательного поиска, в которой цикл содержит не две логические проверки (шаги S2 и S4), а всего одну. В нашем случае это довольно существенно, т. к. описанный выше цикл реализуется пятью-шестью машинными командами и исключение из него даже одной команды эквивалентно повышению производительности на 15—20%.

Содержание Назад Вперед