Методи обчислення адреси

1 Загальна класифікація алгоритмів пошуку

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

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

Інший варіант класифікації-методи, засновані на порівнянні самих значень, і методи, засновані на їх цифрових властивостях. Це так звані методи хешування.

2 Лінійний пошук

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

1. Елемент знайдений, тобто a_i = х.

2. Весь масив проглинутий і збігу не знайдено.

3. Це дає нам лінійний алгоритм.

Звертаємо увагу, що якщо елемент знайдений, то він знайдений разом із мінімально можливим індексом, тобто це перший з таких елементів. Очевидно, що закінчення циклу здійсниться, оскільки на кожному кроці значення i збільшується, і, отже, воно досягне за скінченну кількість кроків межі N; фактично ж, якщо збігу не було, це відбудеться після N кроків.

Int LinearSearch (int[] a, int N, int L, int R, int Key)

{

for (int I = L;i<=R; i++)

if(a[i] = = Key)

return (i);

return (-1); // елемент не знайдений

}

3 Двійковий (бінарний) пошук елемента в масиві

Якщо у нас є масив, що містить впорядковану послідовність даних, то дуже ефективний двійковий пошук.

Змінні Lb і Ub містять, відповідно, ліву і праву межі відрізка масиву, де міститься потрібний елемент. Починаємо завжди з дослідження середнього елементу відрізка. Якщо шукане значення менше від середнього елемента, ми

переходимо до пошуку у верхній половині відрізка, де всі елементи менші від тільки що перевіреного. Іншими словами, значенням Ub стає (М - 1) і на наступній ітерації ми працюємо з половиною масиву. Отже, в результаті кожної перевірки ми удвічі звужуємо область пошуку.

Блок-схема бінарного пошуку подана на рисунок 12.

Рисунок 12 – Блок-схема функції бінарного пошуку за параметром

Функція, що реалізує бінарний пошук, має такий вигляд:

int BinarySearch (int a, int Lb, int Ub, int Key)

{

intM;

do

M = Lb + (Ub-Lb)/2;

//шукаємо середину відрізку

if(Key<a[M])

Ub = —М; //переходимо у ліву частину

else if (Key > а[М])

Lb = ++М; //переходимо у парву частину

else

return (M);

if (Lb > Ub)

return (-1); //не знайдено

while (1);

}

4 Пошук методом Фібоначчі

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

Числа Фібоначчі формуються на основі додавання двох попередніх чисел, де перше і друге число дорівнюють 1. Тобто, можна скласти таку послідовність чисел:

1,1,2,3,5,8,13,21,34...

Блок-схема пошуку методом Фібоначчі подана на рисунку 13.

int find_fibo(int strPar)

{

Int resFind, a[10];

Int q=Fibonachi(1), p=Fibonachi(2), i=Fibonachi(3);

//функція, що визначає число Фібоначчі за номером

int FindResult = -1;

do

{

if(a[i]= strPar)

{

FindResult = i;

curSelRow = i+1;

resFind = a[FindResult];

return (resFind);

}

else

if (if(a[i]> strPar)

if(q= =0)

{

resFind = NULL;

return (resFind);

}

else

{i = i-q; p=q; q=p-q;} //перерахунок наступного числа

else

if(P= =i)

{

resFind = NULL;

return (resFind);

}

else

{

і = i+q; p=p-q; q=q-p;

}

}

while(resFind);

if(FindResult= = -1)

resFind = NULL;

return (resFind);

}

Рисунок 13 – Блок-схема функції пошуку Фібоначчі за параметром.