У овој лекцији желимо да проверимо да ли се у некој колекцији налази одређени елемент, неки важан број или податак, који нам је можда потребан у неким даљим истраживањима или другим деловима програма. Научићемо, на која два начина можемо да спроведемо претрагу нашег низа.
Дефиниција: Претраживање је процес налажења елемента низа, који садржи одређени податак који зовемо кључ.
Секвенцијално или линеарно претраживање је најједноставнији алгоритам за претраживање низова. Испитује се један по један елемент низа све док се не нађе одговарајући елемент или дође до краја низа.
Слика 10.7.Потрага за црвом
Посматрајмо низ целих бројева а дужине n. У наставку ћете се упознати са функцијом која проналази индекс траженог елемента t унутар низа a. Уколико низ не садржи елемент функција ће вратити -1 (повратна вредност).
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
//Funkcija koja vrsi linearno pretrazivanje niza a od n elemenata
static int lpretraga(int []a,int n,int t)
{
//Upravljacka promenljiva i
int i;
/*Jednim prolaskom kroz niz, uvecavanjem promenljive i(premestanjem sa jednog
elementa na drugi), utvrdjujemo da li se trazeni element nalazi unutar niza a*/
for(i = 0;i < n;i++)
{
//Ako je trazeni element u nizu, funkcija ce vratiti njegov indeks
if(a[i] == t)
return i;
}
return -1;
}
static void Main(string[] args)
{
int []a = new int[100];
int i,n;
int t;
//Promenljiva trazeni odgovara indeksu elementa t
int trazeni;
Console.WriteLine("Unesi trazeni element:");
t = int.Parse(Console.ReadLine());
Console.WriteLine("Unesi broj clanova niza:");
n = int.Parse(Console.ReadLine());
Console.WriteLine("Unesi elemente niza:");
for(i=0; i < n ;i++)
{
a[i] = int.Parse(Console.ReadLine());
}
/*Pozivamo funkciju lpretraga da nam prosledi indeks elementa t ili -1
ako element nije pronadjen*/
trazeni = lpretraga(a , n , t);
//Ispisujemo na kojoj se poziciji u nizu a nalazi nas element
Console.WriteLine("Indeks elementa je:"+ trazeni);
}
}
}
Напомена:
Овде смо направили посебну функцију lpretraga за линеарну претрагу низа, коју смо касније позивали у главном методу static void Main(string[] args) са унетим аргументима са стандардног улаза.
Приметите, да ћете, ако додате исту функцију само са while петљом, имати јасан увид да се у свакој итерацији обављају две провере:
да ли је i мање од n и
да ли је a[i]==t.
int lpretraga(int a[] , int n , int t)
{
int i;
//Promenljivu i postavljamo na pocetnu vrednost, tj. na indeks prvog elementa
i = 0;
/*Sve dok ne stignemo do poslednjeg n-tog elementa u nizu,
pitamo se da li je tekuci element a[i] jednak trazenom*/
while(i < n)
{
if(a[i] == t)
return i;
//Prelazimo na sledeci i-ti element u nizu
i = i + 1;
}
//Nema elementa, vracamo -1
return -1;
}
Али, да ли сте се запитали колико је ефикасан овакав алгоритам претраживања?
Слика 10.8. Гужва
Слика 10.9. Новчанице
Слика 10.10. Документи
Слика 10.11. Књиге
Шта ако смо нпр.заборавили број телефона који нам је хитно потребан!?
Није свеједно да ли ћемо у телефонском именику или адресару са бројевима или адресама за хиљаду особа нечији телефон (адресу) тражити из највише 1000 корака (линеарним претраживањем) или применити алгоритам који ће нам омогућити да нађемо потребну информацију у највише 10 корака, зар не? Наравно, ако је тражени податак доступан у том скупу података.
Сећате се шта нам јавља програм ако нема елемента у низу?!
Тај чаробни алгоритам је један напреднији начин претраге, такозвано бинарно претраживање.
Подразумева да је низ претходно сортиран растуће или опадајуће по неком критеријуму. Алгоритам се заснива на идеји да се у сваком кораку одбаци половина могућности. Исти поступак се понавља на одабраној половини све док се не пронађе елемент или док у поднизу након дељења не остане ниједан елемент. То би значило да низ уопште не садржи тражени елемент.
Овај алгоритам врши претраживање низа тако што прво упоређује тражени елемент са средишњим елементом. Уколико он није једнак траженом елементу и захваљујући чињеници да је наш низ сортиран, алгоритам одређује у којој половини (поднизу) се може наћи кључ, а другу половину одбацује.
Сада ћемо претходни поступак демонстрирати на једном једноставном примеру.
Дат је низ бројева 1,2,.....60 у растућем поретку. Рецимо да треба да проверимо да ли се међу њима налази број 47?
Ако бисмо ово радили линеарном претрагом морали би 47 пута да направимо поређење, зато ћемо у наредној функцији видети како то ефикасно решава бинарна претрага.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
//Promenljive donji i gornji predstavljaju levu i desnu granicu pretrazivanja niza
/*Funkcija bpretraga ima za argumente promenljivu a nizovnog tipa, promenljivu n
i promenljivu t koja se trazi*/
static int bpretraga(int a[] , int n , int t)
{
//Pomenute promenljive postavljamo na indekse prvog i poslednjeg elementa niza
int donji = 0;
int gornji = n-1;
//Indeks srednjeg clana niza
int srednji;
while(donji < gornji)
{
srednji = (donji + gornji) / 2;
//Proveravamo da li je t bas sredisnji element
if(a[srednji] == t)
//Ako jeste vracamo njegov indeks
return srednji;
//Proveravamo da li je t u prvoj polovini niza
if(t < a[srednji])
/*Smanjujemo opseg pretrage, tako sto promenljiva gornji
postaje desna granica pretrage prve polovine niza*/
gornji = srednji - 1;
else
//Promenljiva donji postaje leva granica druge polovine niza
donji = srednji + 1;
}
return -1;
}
static void Main(string[] args)
{
int a[] = new int[60];
int i;
int trazeni;
int t;
Console.WriteLine("Unesi trazeni element:");
Console.ReadLine(t);
Console.WriteLine("Unesi elemente niza:");
for (i = 0; i < 60;i++)
{
a[i] = i;
}
//Pozivamo funkciju bpretraga, da pretrazi nas niz od 60 brojeva
trazeni = bpretraga(a , 60 , t);
//Ispisujemo indeks trazenog elementa u konzoli
Console.WriteLine("Indeks elementa je:"+trazeni);
}
}
}
