Основная идея двоичного поиска состоит в том, что мы всегда знаем, что если t вообще есть в массиве, то оно должно быть в выбранном нами поддиапазоне. Мы будем использовать выражение mustbe (range) для отражения того факта, что если t есть в массиве, то оно есть и в исследуемом на данном этане диапазоне range. Мы воспользуемся этой записью, чтобы превратить описание двоичного поиска в набросок программы (листинг 4.1):
Листинг 4.1. Набросок программы двоичного поиска
initialize range to 0 .n-1
/* инициализируем диапазон 0 п-1 */
1 оор
/* цикл */
{ invariant mustbe(range) }
/* инвариант число t должно быть в диапазоне range */ if range is empty, /* если диапазон пуст */ break and report that t is not in array /* цикл завершается, t в массиве нет */ compute m, the middle of the range /* находим m - середину диапазона */ use m as a probe to shrink the range /* используем значение m для сужения диапазона */ if t is found during the shrinking process, break and report its position /* если при этом находим t, */
/* завершаем цикл и возвращаем позицию t */
Важной частью этой программы является инвариант цикла (loop invariant), заключенный в фигурные скобки. Это утверждение, относящееся к состоянию программы, называется инвариантом, поскольку оно остается истинным в начале и в конце каждой из итераций; это формализация того интуитивного утверждения, которое мы сделали выше.
Опубликовал vovan666
April 16 2013 23:57:56 ·
0 Комментариев ·
2731 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
