> 4. [Порівняння.]
if key i then Last: = i-1 else First: = i +1; ШагB 5. [Кінець. ] End do (B 1 )
Блок схема алгоритму бінарного пошуку наведена на малюнку 2.
В
На малюнку 3 наведено приклад визначення key = 42.
В
Crt; {Реалізація алгоритму бінарного пошуку.}
Constn = 1000; key = 100; Arr = Array [1 .. n] of Integer; a: Arr; key, i, n: Integer; BSEARCH (n, key: Integer; a: Arr; Var i: Integer); F, L: Integer; Label LL; F: = 1; L: = n; (L> = F) doi: = (F + L) div 2; If key = a [i] then Goto LL; key {Початок.} i: = 1 to n do a [i]: = i; {Введення даних. } (n, key, a, i); { Сортувати. } ('Кількість елементів =', n: 5, 'Key =', key: 4); {Висновок.} ( a (i ) = ', a [i]: 4; i = , i: 4);
END.
В
Метод бінарного пошуку можна застосовувати для того, щоб представити упорядкований масив у вигляді двійкового дерева. Значення ключа k (8) = 53 є коренем дерева. Інтервали ключів (1-7) і (9-16) поміщаються в пам'ять. Потім на другому кроці в першій і другій половинах визначаються середні елементи. Середні ж елементи визначаються в кожній чверті і т.д. Для даного масиву отримаємо наступне бінарне дерево пошуку (див. малюнок 4).
Нехай N = 2 k -1 - число записів у масиві і двійкове дерево масиву є повним, тобто у кожної вершини є як лівий, так і правий наступники. Дерево має висоту k-1 , а число вершин на рівні i одно 2
