Методические указания. Бинарный поиск предполагает существование между элементами ИМ отношения упорядочения: К1<K2<, ,<Kn

Бинарный поиск предполагает существование между элементами ИМ отношения упорядочения: К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.