Алгоритмы и программы. Афанасьева Т. В - 43 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

43
Рис. 22. Алгоритм метода бинарного поиска
Искомый элемент Х=12.
Элементы массива для рассмотрения А (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)<Х,
исключаем левую половину массива из рассмотрения.
Элементы массива для рассмотрения А (12, 20, 30, 35, 45).
Номера элементов 6 7 8 9 10.
Второе бинарное деление массива: номер элемента S=8, А(8)=30 А(8)>Х,
исключаем правую половину массива из рассмотрения.
Элементы массива для рассмотрения А (12, 20).
Номера элементов 6 7
Третье деление S=6, А(6)=12 А(6)=Х, элемент Х=12 найден.
Рис. 23. Иллюстрация применения метода бинарного поиска
+
+
+
НАЧАЛО
Ввод N,X
A(1...N)
P=1, Q = N
Р< Q
S=(P+Q) DIV 2
КОНЕЦ
A(S)=X
A(S)<X
P=S+1
Найдено
S
Q=S+1
В этом алгоритме Х – искомое
значение, P, Q – номера первого
и последнего элемента массива.
S=(P+Q) DIV 2 – операция
деления нацело массива пополам.
S – результат: номер совпавшего
элемента массива
Значение не
найдено

Страницы