среда, 30 мая 2012 г.

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


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

Комментариев нет:

Отправить комментарий