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

💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

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

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

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

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

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

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

Номер искомого элемента равен 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.