2. Основні методи пошуку.

Метод простого пошуку.

Сутність методу полягає в тому, що елементи масиву послідовно порівнюються зі зразком пошуку. Якщо має місце співпадання, то пошук закінчується. Інакше здійснюється перехід до наступного елементу. Отже, пошук припиняється або при досягненні кінця масиву, або при знаходженні заданого елемента. Оскільки наявність та місцезнаходження елементу наперед невідомі, то  для практичної реалізації алгоритму потрібно застосувати цикл з передумовою. Перевірку  знаходження елементу здійснимо за значенням змінної i, що є індексом поточного елементу масиву. Якщо значення цієї змінної перевищує n (кількість елементів масиву), то елемент не знайдений, а отже, в масиві відсутній.  Алгоритм простого пошуку запишемо у вигляді відповідної процедури.

procedure search;

begin

{починаємо з першого елементу}

i:= 1;

{проводимо пошук}

while (i<=n) and (a[i]<>x) do i: = i+1;

{перевіряємо результат }

if і>n

then writeln ('Елемент  ', x, ' не знайдений')

else writeln ('Елемент ', x, 'знайдений під номером,і);

end.

У наведеній процедурі ми скористалися тим властивістю мови Паскаль, що логічний вираз перестає обчислюватися, коли його значення стає уже відомим. Тому в заголовку циклу while після того, як  виконається перша складова умови  i> n, друга частина умови обчислюватися не буде. Тому відбудеться коректне завершення циклу без звертання до неіснуючого n +1-го елементу масиву.

Метод пошуку з бар’єром.

Перевагою методу простого пошуку  є його простота та наочність. Недоліком методу є те, що у заголовку циклу доводиться здійснювати дві перевірки: на допустимість індексу і на рівність значення. Якби ми знали, що шукане значення точно є десь у масиві, то першу перевірку можна було б не вказувати, що прискорило б пошук. Це наштовхує на думку, у вихідний масив потрібно тимчасово  включити шукане значення. Однак, оскільки розміри масиву змінені бути не можуть, включення можна здійснити на останнє місце масиву. Тоді  після завершення  пошуку потрібно повернути в кінець масиву початкове значення.  Для одержання  результату пошуку потрібно перевірити , чи дорівнює шукане значення тому елементові масиву, на якому відбулось завершення роботи алгоритму. Навіть, якщо елемент у початковому масиві був відсутній, і зупинка була здійснена на включеному в масив зразкові, перевірка результату буде проведена для вихідного елементу масиву, який на той час замінить зразок пошуку. Наведений метод  називається “пошук елементу з бар'єром”. Роль бар’єрного елементу виконує включений в масив зразок пошуку. Включення повинно здійснюватись тільки замість останнього елементу масиву, після якого інших елементів немає. Процедура для даного алгоритму має такий вигляд.

procedure  barrier;

var b: integer;

begin

{Заміняємо останній елемент шуканим значенням, запам'ятовуючи його у змінній b}

b:=a[n];

a[n]:=x;

{пошук}

i:= 1;

while  a[i]<>x do i: = i+1;

{Повертаємо останній елемент}

a[n]: = b;

{Вивід результату}

if a[і] =x

then  writeln ('Елемент знайдений під номером ',і)

else  writeln ('Елемент  не знайдений');

end.

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

Бінарний пошук

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

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

procedure  Binary;

var

k1, k2: integer;

Begin

{початкова частина пошуку  - весь масив}

k1:=1;

k2:=n;

{пошук}

repeat

  i:= (k1+k2) div 2;

  if a[i] < x then k1:= i +1 else k2:= i -1

until (a[і] = x) or (k1 > k2);

{перевірка результату пошуку}

if a[і] = x

then  writeln ('Елемент знайдений під номером ',і)

else  writeln ('Елемент  не знайдений');

End.

Даний метод  дуже ефективний, оскільки, наприклад, для масиву з 1000 елементів результат визначається навіть у гіршому випадку після 10 кроків циклу, у той час як для методів  простого пошуку та пошуку з бар’єром в середньому потрібно буде 500 кроків. Однак впорядкування вихідного масиву є досить трудомісткою операцією, і вимагає часу, значно більшого, ніж проведення пошуку першими двома методами.

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

Вказівки по організацію дослідження часу роботи методів.

Порівняємо швидкість методів простого пошуку і пошуку з бар’єром. Для дослідження візьмемо масив з 30000 елементів. Для визначення часу роботи методів скористаємось стандартною процедурою gettime модуля dos. Вона має наступний формат:

Gettime(h, m, s, ms)

де h – години;

m– хвилини;

s – секунди;

ms – мілісекунди.

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

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

program poisk;

uses dos, crt;

const n=30000;

type massiv=array[1..n] of integer;

var

a:massiv;

x:integer;

i, j:integer;

h1,m1,s1,ms1:word;

h2,m2,s2,ms2:word;

t1,t2:longint;

procedure search;

begin

{починаємо з першого елементу}

i:= 1;

{проводимо пошук}

while (i<=n) and (a[i]<>x) do i: = i+1;

{перевіряємо результат }

if і>n

then writeln ('Елемент  ', x, ' не знайдений')

else writeln ('Елемент ', x, 'знайдений під номером,і);

end.

procedure  barrier;

var b: integer;

begin

{Заміняємо останній елемент шуканим значенням, запам'ятовуючи його у змінній b}

b:=a[n];

a[n]:=x;

{пошук}

i:= 1;

while  a[i]<>x do i: = i+1;

{Повертаємо останній елемент}

a[n]: = b;

{Вивід результату}

if a[і] =x

then  writeln ('Елемент знайдений під номером ',і)

else  writeln ('Елемент  не знайдений');

end.

{ ОСНОВНА ПРОГРАМА }

begin

clrscr;

{}

randomize;

for i:=1 to n do a[i]:=random(10000);

write('Введiть зразок пошуку x=');

readln(x);

writeln('Метод простого пошуку:');

gettime(h1,m1,s1,ms1);

for j:=1 to 100 do search;

getTime(h2,m2,s2,ms2);

{Перетворюємо час до мілісекунд }

t1:=(LongInt(h1)*3600+m1*60+s1)*100+ms1;

t2:=(LongInt(h2)*3600+m2*60+s2)*100+ms2;

writeln('Час пошуку t=',(t2-t1)/100/100:6:4, ' сек');

writeln;

writeln('Метод пошуку з бар’єром:');

gettime(h1,m1,s1,ms1);

for j:=1 to 100 do barrier;

getTime(h2,m2,s2,ms2);

t1:=(LongInt(h1)*3600+m1*60+s1)*100+ms1;

t2:=(LongInt(h2)*3600+m2*60+s2)*100+ms2;

writeln('Час пошуку t=',(t2-t1)/100/100:6:4, ' сек');

writeln;

end.

Результати роботи процедур:

 

Елемент	Час пошуку		Знайдений під номером
	Простий пошук	Пошук з бар’єром
1925	0,0013	0,0007	17923
0	0,0027	0,0015	-