Алгоритмические и математические аспекты поиска достаточно сложны и их исследованию посвящены многочисленные работы. Наиболее полно эти вопросы рассматриваются в ранее упоминавшейся трилогии Д. Кнута. Мы же ограничимся самыми простыми алгоритмами и программами, позволяющими понять суть проблемы и познакомиться с некоторыми подходами к повышению эффективности поиска.
В достаточно общих чертах задача поиска формулируется следующим образом. Имеется массив а, содержащий п однородных объектов (чисел, строк, записей), и нужно установить, содержится ли в нем заданный объект q. При положительном ответе следует дополнительно сообщить порядковый номер (индекс) j найденного объекта (a[j] = q).
Последовательный поиск
Если исходный массив а не упорядочен, то единственно разумным способом является последовательный перебор всех элементов массива и сравнение их с заданным значением. В лучшем случае мы можем получить ответ на первом же шаге, если q = а [ 1 ]. В худшем случае придется перебрать все п элементов и только после этого дать положительный или отрицательный ответ. В среднем количество проверок может оказаться порядка п/2.
Классический алгоритм последовательного поиска включает следующие шаги:
Большинству программистов кажется, что приведенный алгоритм является оптимальным и ничего сократить в нем нельзя. Однако это — очень распространенное заблуждение. Д. Кнут приводит модификацию алгоритма последовательного поиска, в которой цикл содержит не две логические проверки (шаги S2 и S4), а всего одну. В нашем случае это довольно существенно, т. к. описанный выше цикл реализуется пятью-шестью машинными командами и исключение из него даже одной команды эквивалентно повышению производительности на 15—20%.