Задача поиска является фундаментальной в комбинаторных алгоритмах, так как она формулируется в такой общности, что включает в себя множество задач, представляющих практический интерес. При самой общей постановке "Исследовать множество
с тем чтобы найти элемент, удовлетворяющий некоторому условию
", о задаче поиска едва ли можно сказать что-либо стоящее. Удивительно, однако, что достаточно незначительных ограничений на структуру множества
, чтобы задача стала интересной: возникает множество разнообразных стратегий поиска различной степени эффективности. Мы сделаем некоторые предположения о структуре множества
, позволяющие исследовать
или
. Большинство алгоритмов поиска попадает в одну из трех категорий, характеризуемых временем поиска
