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

End.

1.2 Алгоритм пошуку діленням пополам (бінарний пошук)

Очевидно, що ніякого іншого способу підвищення ефективності пошуку в масиві не має, якщо відсутня додаткова інформація про дані. Пошук можна значно покращити, якщо елементи в масиві попередньо будуть впорядковані. Даний метод – ділення пополам ще називають "метод дихотомії", "бінарне дерево". Бінарним деревом його називають тому, що можна схематично зообразити дерево, по якому буде проводитися пошук (Рис. 1).

Рис. 1. Дерево порівнянь, що відповідає бінарному пошуку для N =16

Нехай масив a є впорядкованим по зростанню, тобто

, .

Розглядуваний алгоритм базується на таких принципах :

) вибирається довільно деякий елемент, наприклад a _m ;

) проводиться порівняння a _m з аргументом пошуку x ;

) якщо значення співпадають, то пошук припиняється, якщо a _m <x , то відкидаються з розгляду всі елементи масиву до a _m включно, якщо a _m >x , то відкидаються з розгляду всі елементи масиву після a _m включно.

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

Введемо наступні позначення : L, R - індексні змінні, що відмічають відповідно лівий і правий кінці частини масиву, де ще можна знайти потрібний елемент. Алгоритм такого пошуку можна записати у вигляді послідовності команд :

L:=1; R:=N; f:=true;

while (L<=R) and f do

begin

m:=k; {k - довільне значення між L і R}

if a[m]=x then f:=false else

if a[m]<x then L:=m+1 else R:=m-1

end;

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

Ефективність алгоритму можна дещо покращити. Перевірку на рівність із шуканим ключем можна виконувати в другу чергу, оскільки вона зустрічається лише один раз і приводить до припинення пошуку. Крім того ймовірність точного попадання в потрібне значення є меншою ніж попадання в більше або менше значення. Тому варто поміняти місцями заголовки умовних операторів :

if a[m]<x then L:=m+1 else

if a[m]>x then R:=m-1 else f:=false;

Однак, можна ще покращити ефективність, якщо спростити умову припинення алгоритму. Для цього необхідно відмовитися від бажання припинення пошуку при фіксації співпадання. Тоді пошук продовжуватиметься доти, доки досліджувана частина масиву не стягнеться до одного елемента, який і буде шуканим :

L:=1; R:=N;

while L<R do

begin

m:=(L+R) div 2;