Основы визуальной алгоритмизации

Поиск элементов в упорядоченном массиве


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

Элементы массива А (2,3,4,6,10,12,20,30,35,45).

Номера элементов       1 2 3 4  5   6  7   8   9  10.

Первое деление S=5, А(5)=10 А(5)<Х), исключаем левую половину.

Элементы массива А (2,3,4,6,10,12,20,30,35,45).

Номера элементов       1 2 3 4  5   6  7   8   9  10.

Второе деление S=8, А(8)=30 А(8)>Х), исключаем правую половину.

Элементы массива А (2,3,4,6,10,12,20,30,35,45).

Номера элементов       1 2 3 4  5   6  7   8   9  10.

Третье деление S=6, А(6)=12 А(6)=Х), элемент Х=12 найден.

Рис.30. Иллюстрация применения метода бинарного поиска

На рис.31 представлен алгоритм, реализующий метод бинарного поиска в упорядоченном массиве.

            

        Рис.31.Алгоритм поиска методом бинарного поиска



Содержание раздела