ВУЗ:
ска, и использовал его для дальнейшего сужения области поиска.
Подобный подход к процедуре поиска представлен на рис. 4.13. Здесь демонстрируется способ решения задачи, заклю-
чающейся в определении присутствия имени John в списке, приведенном в левой части рисунка. Прежде всего, анализирует-
ся средний элемент Harry. Так как имя, которое мы ищем, по алфавиту располагается после данного имени, поиск продолжа-
ется в нижней части исходного списка. Средним элементом этой части является имя Larry. Поскольку по алфавиту искомое
имя предшествует данному, поиск следует продолжать в верхней части текущего подсписка. Обратившись к среднему эле-
менту этого вторичного подсписка, обнаруживаем искомое имя John и объявляем поиск успешным. Короче говоря, наша
стратегия состоит в последовательном делении анализируемого списка на меньшие по размеру сегменты до тех пор, пока
либо будет найдено искомое значение, либо поиск сузится до пустого сегмента.
Можно реализовать эту стратегию с помощью нашего псевдокода, модифицировав приведенную на рис. 4.12 программу так,
чтобы учесть возможность получения пустого списка. Модифицированная соответствующим образом программа на псевдо-
коде, которой присвоено имя Search, показана на рис. 4.14. При выполнении этой процедуры и при достижении инструк-
ции "Применить процедуру Search, чтобы ...", мы будем просто применять этот же метод поиска к меньшему
списку, который является частью исходного списка. Если этот вторичный поиск завершится успешно, мы вернемся в исход-
ную процедуру, чтобы объявить выполняемый в ней поиск успешным. Если же вторичный поиск окончится неудачей, мы
объявим неудачным и исходный поиск.
Alice
Bob
Carol
David
Elaine
Fred
George
Harr
y
Irene Irene Irene
Joh
n
Joh
n
Joh
n
Kell
y
Kell
y
Kell
y
Larr
y
Larr
y
Mar
y
Mar
y
Nancy Nancy
Oliver Oliver
Исходный
список
Первый
подсписо
к
Второй
подсписок
Рис. 4.13. Применение стратегии двоичного поиска
для обнаружения имени John в упорядоченном списке
Чтобы увидеть, как представленная на рис. 4.14 процедура выполняет свою задачу, попробуем с ее помощью опреде-
лить, содержится ли значение Bill в списке имен Alice, Bill, Carol, David, Evelyn, Fred, George. Поиск начинается с выбора в
качестве проверяемого элемента имени David (среднего элемента списка). Так как искомое значение (Bill) по алфавиту
предшествует проверяемому, следует применить процедуру Search к списку элементов, предшествующих имени David, т.е.
к списку Alice, Bill, Carol. Для этого нам потребуется создать
Страницы
- « первая
- ‹ предыдущая
- …
- 92
- 93
- 94
- 95
- 96
- …
- следующая ›
- последняя »
