Поиск информации

Поиск информации

Задача поиска обычно формулируется следующим образом. Имеется некоторое хранилище информации — информационный массив (телефонный справочник, словарь, расписание поездов, диск с файлами и др.). Требуется найти в нем информацию, удовлетворяющую определенным условиям поиска (телефон какой-то организации, перевод слова, время отправления поезда, нужную фотографию и т. д.). При этом, как правило, необходимо сократить время поиска, которое зависит от способа организации данных и используемого алгоритма поиска.

Алгоритм поиска, в свою очередь, также зависит от способа организации данных.

Если данные никак не упорядочены, то мы имеем дело с неструктурированным набором данных. Для осуществления поиска в таком наборе применяется метод последовательного перебора.

При последовательном переборе просматриваются все элементы подряд, начиная с первого. Поиск при этом завершается в двух случаях:

— искомый элемент найден;

— просмотрен весь набор данных, но искомого элемента среди них не нашлось.

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

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

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

Если же провести поиск последовательным перебором достаточно много раз, то окажется, что в среднем на поиск требуемого элемента уходит N/2 просмотров. Эта величина определяет длительность поиска — главную характеристику поиска.

Если же информация упорядочена, то мы имеем дело со структурой данных, в которой поиск осуществляется быстрее, можно построить оптимальный алгоритм.

Одним из оптимальных алгоритмов поиска в структурированном наборе данных может быть метод половинного деления.

Напомним, что при этом методе искомый элемент сначала сравнивается с центральным элементом последовательности. Если искомый элемент меньше центрального, то поиск продолжается аналогичным образом в левой части последовательности. Если больше, то — в правой. Если же значения искомого и центрального элемента совпадают, то поиск завершается.

Пример 4. В последовательности чисел 61 87 180 201 208 230 290 345 367 389 456 478 523 567 590 требуется найти число 180.

Процесс поиска представлен на схеме:

⇐ Предыдущая 1 234 5 Следующая ⇒