Алгоритмы и программы. Афанасьева Т. В - 42 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

42
2.9. Алгоритмы обработки упорядоченных массивов
Рассмотренные выше алгоритмы сортировки считаются одними из
важнейших процедур упорядочивания структурированных данных,
хранимых в виде массивов. Одной из главных целей задач сортировки
массивов является облегчение их дальнейшей обработки, так как для
упорядоченных данных разработаны эффективные методы поиска и
обновления. Так, например, поиск минимального или максимального
значения в упорядоченном массиве сводится
к выборке первого или
последнего элемента массива. Рассмотрим алгоритм поиска произвольного
элемента в упорядоченном массиве.
Задача поиска значения Х в упорядоченном по возрастанию
значений массиве A(1)<A(2)<,...,<A(n) формулируется следующим
образом. Требуется выяснить, входит ли значение Х в этот упорядоченный
массив, и если входит, то определить значение k, для которого А(k)=Х. Для
такого типа
задач применяется эффективный метод бинарного поиска,
который также известен как метод деления пополам.
Сущность этого метода поиска заключается в последовательном
определении номера S элемента, расположенного в точке деления
упорядоченного массива пополам и сравнении искомого значения Х с этим
элементом массива A(s). Если A(s)=Х, то поиск заканчивается.
В противном случае возможны две ситуации.
Если A(s)<Х, то все элементы, имеющие номера с 1 по s, также
будут меньше Х, если A(s)>Х, то все элементы, имеющие номера с S по n,
также будут больше Х в силу упорядоченности массива по
возрастанию значений.
Поэтому для дальнейшего поиска половину значений массива можно
исключить из рассмотрения. В первом случае – левую, во втором
случае –
правую половину. Рассмотрим пример. Допустим, что требуется
определить, совпадает ли значение Х=12 с каким-либо элементом в
упорядоченном массиве А и, если совпадает, то определить порядковый
номер S этого элемента. Иллюстрация применения метода бинарного
поиска для поиска элемента Х=12 в массиве (2, 3, 4, 6, 10, 12, 20, 30, 35, 45)
приведена на рис. 23.
На рис. 22 представлен алгоритм, реализующий метод
бинарного
поиска в упорядоченном массиве.

Страницы