Двоично търсене
1) без използване на запушалка
var A:array[0..N-1] of Any;
writeln('Въведете елементи от масива:');
за i:=0 до N-1 направи
докато (i>N) и (A[i]<b) правят
writeln('Намерен ключ за съвпадение на елемент. Позиция на елемент -',i+1)
writeln('Няма елементи, отговарящи на ключа');
2) с помощта на запушалка
var A:array[0..N] of Any;
writeln('Въведете елементи от масива:');
за i:=0 до N-1 направи
writeln('Намерен ключ за съвпадение на елемент. Позиция на елемент -',i+1)
writeln('Няма елементи, отговарящи на ключа');
Трябва да се отбележи, че като цяло линейното търсене сред N елемента изисква средно N/2 сравнения в случай на успешно търсене и N сравнения в най-лошия случай и следователно разходите за време за големи масиви са големи.
Този алгоритъм се прилага, ако няма допълнителна информация за данните от масива.
Очевидно няма начин да се ускори търсенето, ако няма информация за данните, сред които се търси. Известно е също, че ако данните са подредени, търсенето може да стане много по-ефективно. Следователно, помислете за алгоритъм, който се основава на факта, че масивът A е подреден (т.е. a[i-1]
Същност: вземете средния елемент на масива и го сравнете с ключа. В резултат на това са възможни 3 случая:
1) ако елементът на масива е равен на ключа, тогава търсеният елемент е намерен;
2) ако елементът на масива е по-малък от ключа, тогава всички елементи на масива с индекси по-малки от N/2 се изключват от разглеждане;
3) ако елементът на масива е по-голям от ключа, тогава всички елементи на масива с индекси, по-големи от N/2, се изключват от разглеждане;
След това търсенето продължава в една от половините на масива по същия начин.
варA:масив[0..N] от Any;
writeln('Въведете подредена последователност от елементи на масива');
за i:=0 до N направете readln(A[i]);
m:=(ляво+дясно) div 2;
ако (Right<N) или ((Right=N) и (a[N]=b)), тогава
writeln(' Намерен имейл. Позиция на имейл: ',Дясно)
writeln(' Няма елемент ');
Намирането на елемент чрез двоично търсене е много бързо. Търсенето сред N елемента изисква log2(N) сравнения в най-лошия случай. В допълнение, двоичното търсене вече при N от порядъка на 100 е много по-ефективно от линейното търсене - както по отношение на скоростта на откриване, така и по отношение на възможността за получаване на отрицателен резултат. За да докажа това, ще дам следните характеристики на линейното и двоичното търсене:
1) линейно търсене:
среден брой сравнения при наличие на елемент: 5
брой сравнения при липса на елемент: 10
среден брой сравнения при наличие на елемент: 500
брой сравнения при липса на елемент: 1000
среден брой сравнения в присъствието на елемента: 500 000
брой сравнения при липса на елемент: 1000000
1) двоично търсене:
максимален брой сравнения при наличие на елемент: 8
максимален брой сравнения при липса на елемент: 8
максимален брой сравнения при наличие на елемент: 10
максимален брой сравнения при липса на елемент: 10
максимален брой сравнения при наличие на елемент: 20
максимален брой сравнения при липса на елемент: 20
Представете си, че търсите дума в речник. Малко вероятно е първо да погледнем в средата на речника, след това да се оттеглим от началото с 1/4 или 3/4 и т.н., както при двоично търсене.
Ако точната думазапочва с буквата „А“, тогава има смисъл търсенето да започне в началото на речника. Когато бъде намерена началната точка за търсене, по-нататъшните действия няма да приличат много на описаните по-горе методи.
Стигаме до алгоритъм, наречен интерполационно търсене. Нека е даден масив от записи R1,R2. Rk, оборудвани съответно с ключове K1, K2. Кн. Необходимо е да се намери запис с даден ключ K. Тогава, ако е известно, че K се намира между Kl и Ku, тогава следващата проба се прави приблизително на разстояние (u-l) * (K-Kl) / (Ku-Kl) от l, като се приема, че ключовете са числа, които нарастват приблизително като аритметична прогресия.
Интерполационното търсене изисква средно около log2 log2 N стъпки и затова е за предпочитане пред двоичното търсене, когато работите с големи масиви.
Търсене на подниз в низ.
Нека са дадени низ s и подниз p. Тогава за търсене на подниза p в низа s може да се използва следният алгоритъм:
докато (j=lp) или (i=lp-ls) или (i>ls);
if (j=lp) and (lp<>1) then writeln(' Подниз в низ е ');
if i>ls then writeln('Няма поднизове в низа');
Алгоритъмът е ефективен, ако несъответствието между символите на низа и подниза възникне след няколко сравнения във вътрешния цикъл. Но ако съвпадението е намерено в края на низа, тогава са необходими lp*ls сравнения.
Алгоритъм на Кнут, Морис и Прат (KMP)
Този алгоритъм е създаден през 1970 г. и е получил името си от имената на своите разработчици. Състои се от два етапа: подготвителен и основен.
На подготвителния етап се взема предвид структурата на подниза. За целта се формира масив D, който отчита съвпадението на символите на подниза с началото на подниза, както следва: нулевият елемент на масива D получава стойност, равна на -1. По-нататък за всекипозиция j, съвпадаща с началото на подниза, се изчислява максималния брой знаци пред него. Ако няма съвпадения, тогава съответният елемент от масива D е равен на -1. Размерността на масива D е равна на дължината на подниза.
Сега нека да разгледаме основната сцена. Търсенето започва със сравняване на първия знак на низа с първия знак на подниза. В случай на несъответствие, поднизът се измества с броя знаци, посочени от съответния елемент на масива D. Ако няма съвпадение между подниза и низа (т.е. няма даден подниз в низа), тогава програмата ще излезе от цикъла, за да търси подниза, когато i е равно на дължината на низа, т.е. ако никой знак от подниза не съвпада с който и да е знак от низа, тогава програмата ще извърши N сравнения, ако се открият съвпадения на отделни елементи на подниза (но не на целия подниз с низа), тогава в най-лошия случай са необходими N+M сравнения. Ако съвпадението на подниза с низа бъде открито незабавно, тогава ще са необходими M сравнения.