Поиск данных

Постановка задачи поиска данных Первый атрибут: набор данных –совокупность данных, среди которых осуществляется поиск; –Элементы набора называются записями; –Записи состоят из полей; Второй атрибут: ключ поиска –Поле записи, по значению которого происходит поиск; Третий атрибут: критерий поиска –Условие, которому должно удовлетворять значение ключа поиска в искомой записи.

От чего зависит время поиска? как организован набор данных в информационном хранилище; каким алгоритмом поиска пользуются.

Организация набора данных Данные могут быть не организованы; Данные структурированы (данные упорядочены) Структурированные системы данных, хранящиеся на каких-либо носителях, называют структурами данных.

Последовательный поиск Последовательный перебор всех элементов множества до нахождения нужного; Число просмотров при последовательном поиске приблизительно равно N/2, где N - размер набора данных.

Алгоритм последовательного перебора Начало поиска Имеются непроверенные элементы? Выбрать очередной элемент Выполняется критерий поиска? Искомые данные получены Искомые данные не обнаружены Конец поиска

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

Если максимальное число диапазона N не равно целой степени двойки, то оптимальное количество вопросов не будет постоянной величиной, а будет равно одному из двух значений: X или X+1, где 2 X < N < 2 X+1 Пример: Искомое число в диапазоне от 1 до 7, то его можно угадать за 2 или 3 вопроса 2 2 < N < 2 3

Блочный поиск Несколько страниц, помеченных одной буквой – блок; Индекс – часть ключа поиска; Блочно-последовательный метод: 1) с помощью алфавитного индекса выбирается блок с нужной буквой; 2) внутри блока поиск производится путем последовательного перебора.

Поиск в иерархической структуре Многоуровневые блочные структуры хранения данных называются иерархическими структурами. –В файловой системе блоки это каталоги. –Чтобы найти файл, нужно знать путь к файлу по дереву каталога. –Метод поиска в дереве каталогов называют методом спуска по дереву каталогов.