Теперь займемся усовершенствованием нашей программы
Теперь займемся усовершенствованием нашей программы, заботясь о сохранности инварианта в ходе всех наших действий. Прежде всего, нам нужно как-то представить диапазон. Для этого мы будем использовать два индекса I и и, задающие нижнюю и верхнюю границы диапазона L.u. Функция двоичного поиска в разделе 9.3 главы 9 представляет диапазон другим способом: заданием его начала и длины. Логическая функция mustbe(l, и) утверждает, что если число t вообще есть в массиве, то оно обязательно принадлежит диапазону х[1. .и], включая границы диапазона.
Затем нужно заняться инициализацией. Какими должны быть значения I и и, чтобы утверждение mustbe(l, и) было истинным? Очевидный выбор: 0 и п-1: утверждение mustbe(0, п-1) сводится к тому, что если t есть в массиве х, то оно принадлежит а именно это и известно нам с самого начала. Следовательно, инициализация будет состоять в присваивании значений 1=0 и u=n-l.
Затем нужно проверить диапазон на наличие в нем вообще каких-либо элементов, после чего найти его середину т. Диапазон L.u является пустым, если 1>и, и в этом случае мы помещаем в переменную р специальное значение -1, завершая цикл.
if (1>и)
р=-1. break
Оператор break завершает внутренний цикл, к которому он относится. Следующее выражение вычисляет значение m (середину диапазона):
m = (1+u ) / 2
Здесь используется целочисленное деление: 6/2=3, и 7/2=3. Итак, наша усовершенствованная программа выглядит теперь следующим образом (листинг 4.2):
Листинг 4.2. Вторая версия программы двоичного поиска
1 = 0. и = п-1
1 оор
{1 nvan ant. mustbe( 1 . u) } if l>u
p= -1. break m = (1 + u) /2
use m as a probe to shrink the range 1 u if t is found during the shrinking process, break and note its position.
/ русский перевод см в предыдущем листинге */
Опубликовал vovan666
April 16 2013 23:57:58 ·
0 Комментариев ·
2803 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
