§ № Поиск методом половинного деления
Методом половинного деления в последовательности чисел 061 087 154 180 208 230 290 345 367 389 456 478 523 567 590 612 требуется найти число 590. Опишите процесс поиска.
Решение
Последовательность упорядочена по возрастанию, поэтому после сравнения с центральным числом можно отбрасывать ту часть, где находиться не может. По правилу § при длине рассматриваемой части номер центрального элемента равен , где квадратные скобки означают целую часть. Поэтому для чисел берём -е число, а для чисел — -е.
| Просмотр |
Рассматриваемые числа |
Центральное число |
Сравнение и действие |
|
–, чисел |
|
; оставляем числа справа от |
|
–, чисел |
|
; оставляем числа справа от |
|
, , |
|
; число найдено |
На первом шаге , а девятое число — . После него остаются , , , , , , . На втором шаге , а четвёртое число этой части — . Справа от него остаются , , . На третьем шаге , второе число равно искомому . Всего понадобилось просмотра; при последовательном переборе до пришлось бы просмотреть чисел.
Ответ
Число найдено за просмотра: сравнения с , и .
