Курсовая работа: Порівняльний аналіз ефективності та складності алгоритмів пошуку елементів у масивах

end;

Умова припинення циклу L>=R досягається. Адже для цілочисельного серединного значення m справедлива нерівність L<=m<R , якщо попередньо виконувалася умова L<R . Отже, або L збільшується при присвоєнні йому значення m+1 , або R зменшується при присвоєнні йому значення m . Таким чином, різниця R-L на кожному кроці зменшується, і при досягненні нульового значення (L=R) повторення циклу припиняється.

Варто зауважити, що виконання умови L=R ще не гарантує знаходження потрібного ключа. Потрібно враховувати, що елемент a[R] в порівнянні ніколи участі не бере. Тому необхідна додаткова перевірка після циклу на рівність a[R]=x .

Розглянутий алгоритм як і алгоритм лінійного пошуку знаходить шуканий елемент з найменшим індексом, тобто перше входження в масив. А простий бінарний пошук - довільний із співпадаючих елементів.

Реалізація алгоритму на Turbo Pascal. Нехай дано впорядкований масив елементів цілочисельного типу, знайти заданий елемент і вивести його позицію у масиві використовуючи бінарний пошук.

Program Seach_1_2;

Uses Crt;

Const n=10;

Var a:array [1..n] of integer;

i, k,l,r:integer;

Begin

ClrScr;

For i:=1 to n do

Readln (A[i] );

Writeln(‘Vvedit k’);

Readln(k);

l:=1; r:=n;

while l<r do

begin

i:=(l+r) div 2;

if a[i]<k then l:=i+1

else r:=i

end;

Writeln(‘element ’,k,’ mae index ‘,i +1 );

Readln;

End.

1.3 Пошук по "дереву Фібоначе".

Існує ще один метод подібний до методу описаного вище, проте ефективність його дещо вища ніж пошуку по бінарному дереву, хоча така ж пропорціональність log(2)N . В дереві Фібоначе числа в дочірніх вузлах відрізняються від батьківських на одну і ту ж величину, а саме на число Фібоначе (рис. 2.).

Суть даного метода в тому, що порівнюючи наше шукане значення з наступним значенням в масиві, ми не ділимо навпіл нову зону пошуку, як в бінарному пошуку, а відступаємо від попереднього значення, з яким порівнювали, в потрібну сторону на число Фібоначе.