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