|
|
Двійковий (бінарний) пошук елемента в масиві
Якщо у нас є масив, що містить впорядковану послідовність даних, то дуже ефективний двійковий пошук. Змінні 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); }
Пошук методом Фібоначчі
Він працює швидше, ніж бінарний пошук, оскільки замість операцій ділення, що застосовуються у попередньому методі, використовує операції додавання та віднімання. Суть методу полягає у визначенні наступного елемента для порівняння з числами Фібоначчі (звідси і назва). Зменшення індекса означає перехід по попереднього числа, збільшення - перехід до наступного. Числа Фібоначчі формуються на основі додавання двох попередніх чисел, де перше і друге число дорівнюють 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 – Блок-схема функції пошуку Фібоначчі за параметром.
М-блоковий пошук
Цей спосіб зручний при індексному збереженні списку. Передбачається, що вихідний упорядкований список В довжини N розбитий на М підсписків B=B1,B2,..,Bm довжини N1, N2,...,Nm, таким чином, що B=B1,B2,..,Bm. Для знаходження ключа V, треба спочатку визначити перший зі списків Вi, і=1,...,М, останній елемент якого більше V, а потім застосувати послідовний пошук до списку Ві. Збереження списків Ві може бути зв'язним чи послідовним. Якщо довжини всіх підсписків приблизно рівні і M=N, то Мах М-блокового пошуку дорівнює 2N. При однаковій частоті використання елементів Avg M- блокового пошуку дорівнює N. Описаний алгоритм ускладнюється, якщо не відомо, чи дійсно в списку є елемент, що збігається з ключем V. При цьому можливі випадки: або такого елемента в списку немає, або їх кілька. Якщо замість ключа V є упорядкований список ключів, то послідовний чи М-блоковий пошук може виявитися зручнішим, ніж бінарний, оскільки нетреба повторної ініціалізації для кожного нового ключа зі списку V.
Методи обчислення адреси
Нехай у кожному з М елементів масиву Т міститься елемент списку (наприклад, ціле позитивне число). Якщо є деяка функція Н(V), що обчислює однозначно по елементі V -ого адресу- ціле позитивне число з інтервалу [0,М-1 ], то V можна зберігати в масиві T з номером H(V) тобто V=T(H(V)). При такому збереженні пошук будь-якого елемента відбувається за постійний час, не залежний від М. Масив Т називається масивом хешування, а функція Н- функцією хешування. При конкретному застосуванні хешування зазичай є визначена область можливих значень елементів списку V і деяка інформація про них. На основі цього вибирається розмір масиву хешування М і будується функція хешування. Критерієм для вибору М і Н є можливість їхнього ефективного використання. Нехай треба зберігати лінійний список з елементів K1,K2,..,Kn, таких, що при Кi=Кj, mod(Ki,26)= mod(Kj,26). Для збереження списку виберемо масив хешування T(26) із простором адрес 0-25 і функцію хешування H(V)= =mod(V,26). Масив Т аповнюється елементами Т(Н(Кi))=Кi і Т(j)=0, якщо j є у (H(K1), Н(К2),..,Н(Кn)). Пошук елемента V y масиві Т із присвоюванням Z його індексу, якщо V міститься в Т, чи -1, якщо V не міститься в Т, здійснюється так:
int t[26],v,z,i; i=(int)fmod((double)v,26.0); if(t[i]= =v) z=i; else z= -1;
Додавання нового елемента V y список з поверненням у Z індексу елемента, де він буде зберігатися, реалізується фрагментом
z=(int)fmod((doule)v,26.0); t[z]=v;
а виключення елемента V зі списку присвоєнням
t[(int)fmod((double)v,26)]=0;
Тепер розглянемо складніший випадок, коли умова Ki=Kj H(Ki)=H(Kj) не виконується. Нехай V— множина можливих елементів списку (цілі позитивні числа), у якому максимальна кількість елементів дорівнює 6. Візьмемо М=8 і як функцію хешування виберемо функцію H(V)=mod(V,8).
Контрольні питання
1. Наведіть приклади використання алгоритмів пошуку. 2. Поясність особливості алгоритмів пошуку рядків. 3. Порівняйте алгоритми лінійного та бінарного пошуку. 4. Навіть алгоритми пошуку рядків. 5. Назвіть найефективніші методи пошуку рядків.   ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...  ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...  Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
