Даже если на этапе разработки все было проделано наилучшим образом, программиста зачастую ожидает написание весьма сложного кода. Эта глава посвящена одной задаче, для которой требуется особенно аккуратное кодирование, — двоичному поиску. Мы уже рассмотрели ранее эту проблему и сделали набросок алгоритма. Теперь мы воспользуемся основными принципами верификации, чтобы правильно написать программу.
Впервые мы столкнулись с двоичным поиском в разделе 2.2 (см. главу 2), где нужно было определить, содержит ли отсортированный массив х [0. .п-1] элемент t . Мы точно знали, что п неотрицательно и что каждый последующий элемент массива не меньше предыдущего. Кроме того, мы знали, что если п=0, то массив пуст. Тип элементов t и х совпадает; псевдокод работает одинаково хорошо с целыми и вещественными числами и со строками. Ответ помещается в целое число р (от слова позиция); если элемент в массиве отсутствует, в р помещается число -1. В противном случае р неотрицательно и не превышает п-1, и t==x[p].
Алгоритм двоичного поиска решает задачу, уменьшая размер поддиапазона, в котором может находиться t (если это число вообще есть в массиве). В начале диапазоном является весь массив. Затем его средний элемент сравнивается с t, после чего половина диапазона исключается из рассмотрения. Процесс продолжается до тех пор, пока число t не будет найдено или пока диапазон, в котором оно должно находиться, не окажется пуст. Для массива из п элементов двоичный поиск выполняет около log2 п сравнений.
Опубликовал vovan666
April 16 2013 23:57:52 ·
0 Комментариев ·
3179 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.