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