6. Что такое ключ записи и аргумент поиска?

7. Каково возможное минимальное и максимальное число сравнений при последовательном поиске?

8. Что такое “самоорганизующийся файл”?

9. Чем различаются первичные и вторичные ключи?

10. 2.6. Лабораторная работа № 6. Бинарный поиск в информационном массиве.

Цель работы: изучение метода бинарного поиска и его алгоритма.

Методические указания.

Бинарный поиск предполагает существование между элементами ИМ отношения упорядочения: К1<K2<,…,<Kn. Поэтому перед началом поиска необходимо провести сортировку массива. Алгоритм бинарного поиска состоит в следующем. Аргумент поиска сравнивается со средним элементом Км из массива ключей {K1, K2, …, Kм}, причем индекс М среднего элемента вычисляется по формуле.

где L – нижняя граница; K – верхняя граница; | Х | – ближайшее целое, меньшее или равное Х.

Для исходного массива L=1, K=N. Результат сравнения позволит определить, в какой половине файла продолжать поиск.

Если Км=z, то искомый элемент найден.

Если Км<z, то L=M+1.

Если Км>z, то K=M-1.

К выбранной половине файла с границами L и К применяется та же процедура. Если интервал пустой, т.е. L>К, то поиск неудачен. Иначе процесс повторяется: пока средний элемент интервала не будет равен аргументу поиска.

В данной работе в качестве ИМ используется упорядоченная последовательность целых чисел, разрядность которых с учетом знакового разряда не должна превышать 5, а количество элементов массива не должно превышать 50. Ключом элемента является само число. Значение границ, номер среднего элемента и сообщение о результатах поиска выводится на печать.

Приведем пример бинарного поиска в массиве из 6 чисел.

Дано: К={-50; -37; 2; 7; 559; 10001}, z=7.

L=1 К=6 М=3 К(3)=2 2<7

L=4 К=6 М=5 К(5)=5 559>7

L=4 К=4 М=4 К(4)=7 7=7

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

Организацию бинарного поиска для анализа числа сравнений удобно представить в виде бинарного оптимального дерева. Бинарным деревом называется древовидная структура с двоичным ветвлением. В качестве оптимального (в смысле организации поиска) дерева определяют дерево, ветви которого имеют в высоту от h до h-1, где h – высота дерева. Тогда при 2^h-1  N < 2^h удачный поиск требует (min = 1, max = h) сравнений. Неудачный поиск требует h сравнений при N = 2^h - 1, либо h-1 или h сравнений при 2^h-1  N  2^h-1-1.

Блок-схема, реализующая бинарный поиск, представлена в Приложении 5.

Порядок выполнения работы.

1. Ознакомится с общими методическими указаниями и с описаниями данной работы. Ознакомиться по литературе с основными понятиями обработки ИМ, алгоритмами поиска и требованиями к ним.

2. Изучить блок-схему, реализующую бинарный поиск в ИМ (Приложение 6).

3. Каждому студенту взять из таблицы (лабораторная работа № 5) массив из n ключей {K1,K2, … ,Kn} и набор значений аргумента поиска Z.

4. Из данного массива ключей {K1,K2, … ,Kn} получить массив {К1’, К2’,…, Кj’} путем исключения дублирующих значений ключей.

5. Записать элементы массива {К1’, К2’,…, Кj’} в порядке возрастания их значений. Провести поиск в полученном массиве вручную, используя лишь одно (любое) из данных значений аргумента поиска (см. пример).

6. Провести сортировку массива {К1’, К2’,…, Кj’} любым из ранее изученных методов.

7. Провести поиск в отсортированном массиве на ЭВМ, задавая по очереди все данные значения аргумента поиска.

8. Построить бинарное дерево поиска в отсортированном массиве для всех значений аргумента поиска. Оценить число сравнений при поиске.