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

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

Вспомните, как часто и какую информацию приходится искать вам, членам вашей семьи, вашим друзьям и знакомым. Приведите примеры.

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

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

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

1) искомый элемент найден, при этом может быть просмотрена как часть имеющегося набора данных, так и весь набор, если искомый элемент оказался последним в наборе;

2) просмотрены все элементы имеющегося набора данных, но искомого элемента среди них не оказалось.

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

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

Ранее мы уже рассматривали метод половинного деления. Он применяется к наборам данных, элементы которых упорядочены по неубыванию, т. е. каждый последующий элемент не меньше (больше или равен) предыдущего:

а₁ ≤ а₂ ≤ а₃ ≤ ... a_N.

Искомый элемент сравнивается с центральным элементом последовательности, номер которого находится как [N/2] + 1. Квадратные скобки здесь обозначают, что от результата деления берётся только целая часть, а дробная часть отбрасывается.

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

Рассмотрим работу этого алгоритма поиска информации на примере.

Пример 6. В последовательности чисел

061 087 154 180 208 230 290 345 367 389 456 478 523 567 590 612

требуется найти число 180.

Просмотр 1. Работаем со всей последовательностью. Определяем центральный элемент (он подчёркнут):

061 087 154 180 208 230 290 345 367 389 456 478 523 567 590 612

Сравниваем искомый элемент с центральным.

По результатам сравнения отбрасываем правую часть последовательности.

Просмотр 2. Работаем с левой частью последовательности. Определяем центральный элемент (он подчёркнут):

061 087 154 180 208 230 290 345

Сравниваем искомый элемент с центральным.

По результатам сравнения отбрасываем правую часть последовательности.

Просмотр 3. Работаем с левой частью последовательности. Определяем центральный элемент (он подчёркнут):

061 087 154 180

Сравниваем искомый элемент с центральным.

По результатам сравнения отбрасываем левую часть последовательности.

Просмотр 4. Работаем с правой частью последовательности. Определяем центральный элемент (он подчёркнут):

180

Центральный элемент совпадает с искомым. Поиск завершён.

Как связаны длительность поиска методом половинного деления и длина исходной последовательности данных?