Постоянные читатели

суббота, 20 декабря 2014 г.

Поиск данных. Метод половинного деления.

Во всех компьютерных информационных системах поиск данных является основным видом обработки информации. При выполнении любого поиска данных имеются три составляющие, которые мы называем атрибутами поиска. 
Первый атрибут: набор данных. Это вся совокупность данных, среди которых осуществляется поиск. Элементы набора данных будем называть записями. Запись может состоять из одного или  нескольких полей. 
Второй атрибут: ключ поиска. Это поле записи, по значению которого происходит поиск. Например, поле ФАМИЛИЯ.
Третий атрибут: критерий поиска,  или условие поиска. Это то условие, которому должно удовлетворять значение ключа поиска в искомой записи.
Данные могут структурированными или неструктурированными ("куча"). 


Организация набора данных
1)   Неструктурированный набор
2)    Структура данных:
  • Линейная упорядоченность по ключу;
  • Блочная одноуровневая структура;
  • Блочная многоуровневая структура.


Алгоритмы поиска
  • Последовательный поиск - поиск в неструктурированных данных  производится последовательным перебором всех элементов множества
  • Блочный поиск. Записная книжка с вырезанными "лесенками"
  • Поиск в иерархической структуре данных. Дерево каталогов
  • Поиск половинным делением.
В качестве примера поиска с использованием метода половинного деления, можно привести ситуацию, когда мы ищем нужную нам страницу в книге. Мы открываем середину, понимаем, в какой половине находится нужная нам страница, затем ищем середину этой половины и т.д. Кроме этого, при помощи букв алфавита мы можем осуществлять поиск с использованием этого метода в орфографических словарях, в словарях с переводами слов с иностранного языка.

Комментариев нет:

Отправить комментарий