Алгоритмы обработки упорядоченных массивов

Рассмотренные выше алгоритмы сортировки считаются одними из важнейших процедур упорядочивания структурированных данных, хранимых в виде массивов. Одной из главных целей задач сортировки массивов является облегче-ние их дальнейшей обработки, так как для упорядоченных данных разработаны эффективные методы поиска и обновления. Так, например, поиск минимального или максимального значения в упорядоченном массиве сводится к выборке первого или последнего элемента массива. Рассмотрим алгоритм поиска произ-вольного элемента в упорядоченном массиве.

Задача поиска значения Х в упорядоченном по возрастанию значений массиве 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 представлен алгоритм, реализующий метод бинарного поиска в упорядоченном массиве.

Задания для самостоятельного выполнения

Цель заданий. Приобрести умения в синтезе формальной и алгоритмической моделей решения задач. Сформировать компетенции анализа и синтеза при решении простых задач циклической обработки значений массива.

Порядок выполнения. Составить формальное и алгоритмическое

решения следующих задач обработки значений массивов:

1. В одномерном массиве определить первый отрицательный элемент и его номер.

2. Исключить из массива а1,…, аn первый отрицательный элемент.

3. Ввести массив a1, a2,..., a15. Расположить ненулевые элементы по убыванию.

4. Ввести массив x1,x2,...,x20. Элементы на нечетных местах,

расположить в порядке возрастания, а на нечетных – в порядке убывания.

5. Ввести массив a1,a2,...,a15. Требуется упорядочить его по возрастанию

абсолютных значений элементов.

6. Ввести массив x1,x2,...,x20. Требуется расположить отрицательные

элементы в порядке убывания.

7. Ввести упорядоченный по не убыванию массив