Даже если на этапе разработки все было проделано наилучшим образом, программиста зачастую ожидает написание весьма сложного кода. Эта глава посвящена одной задаче, для которой требуется особенно аккуратное кодирование, — двоичному поиску. Мы уже рассмотрели ранее эту проблему и сделали набросок алгоритма. Теперь мы воспользуемся основными принципами верификации, чтобы правильно написать программу.
Впервые мы столкнулись с двоичным поиском в разделе 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 Комментариев ·
3207 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
