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

l:=1; r:=n; i:=1;

while r>l do

begin

i:=(((r-l)*(K-a[l])) div (a[r]-a[l]));

if (K<a[i])then r:=i-1

else l:=i+1;

if K=a[i] then Writeln('element ',k,' mae index ',l);

end;

readln;

End.

Розділ ІІ. Пошук підрядка в рядку

2.1 Прямий пошук підрядка

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

Нехай задано масив a із N елементів та масив b із M елементів, які називаються відповідно базовим рядком та підрядком або образом, причому :

a : array [1..N] of basetype ; b : array [1..M] of basetype ;

Пошук рядка передбачає встановлення першого входження образа b в базовий рядок a .

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

x y z t u x y t

x y t

x y z t u x y t

x y t

x y z t u x y t

x y t

x y z t u x y t

x y t

x y z t u x y t

x y t

x y z t u x y t

x y t