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