Cautarea unei valori dintr-un tablou unidimensional citit de la tastatura sau dintr-un fisier.
1.Cautarea secventiala
Presupune parcurgerea secventiala a unui tablou unidimensional si compararea fiecarui element din tablou
Operaţia de căutare a unei valori (de fapt a primei sale apariţii) într-un
tablou presupune efectuarea operaţiei de parcurgere a acestuia.
val i
(n=7)
Fig. 1. Căutarea
secvenţială
|
Structura de
date tablou permite accesul direct la fiecare componentă a sa într-un timp
egal cu O(1). Ca urmare, complexitatea operaţiei de căutare
într-un tablou oarecare este determinată de complexitatea operaţiei de
parcurgere a acestuia şi este, în cazul cel mai nefavorabil, egală cu O(n), unde n este numărul de elemente al tabloului (Fig. 1).
|
#include <iostream>
using namespace std;
int main()
{
int n, a[100], i, x, gasit=0;
//se citesc datele de intrare
cout<<"n=";cin>>n;
for (i=0;i<n;i++){
cout<<"a["<<i<<"]="; cin>>a[i];
}
cout<<"x=";cin>>x;
// se cauta valoarea lui x printre elementele vectorului a
i=0;
while ((i<n) and (gasit==0))
if (a[i]==x)
gasit=1;
else
i++;
//se afiseaza rezultatele
if (gasit==1)
cout<<"Numarul "<<x<< " se afla in vector pe pozitia a "<<i+1;
else
cout<<"Numarul "<<x<< " nu se afla in vector.";
return 0;}
acelasi program rezolvat altfel dar fara afisarea pozitiei:
#include <iostream>
using namespace std;
int main()
{
int x[100],n,a,i,gasit=0;
cout<<"n= ";cin>>n;
for(i=1;i<=n;i++)
{cout<<"x["<<i<<"]= ";
cin>>x[i];}
cout<<endl<<"a= ";
cin>>a;
for(i=1;i<=n;i++)
{if(a==x[i])
gasit=1;}
if(gasit==1)
cout<<"Numarul "<<a<<" se gaseste in sir.";
else
cout<<"Numarul "<<a<<" nu se gaseste in sir.";
}
sau
Acest algoritm cauta elementul succesiv in componentele vectorului. Un caz practic ar fi exemplul cautarii unui nume in cartea de telefon. Deschidem cartea la intamplare,dorim sa cautam numele “Popa Andrei “. Verificam daca numele se afla in prima partea a cartii sau in a doua parte. Continuam cautarea in portiunea respectiva, actiunea se repeta pana la gasirea numelui.
La fel este si in cazul numerelor dintr-un vector.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <iostream>int main(){ int n,v[100],i,gasit=0,x; cout<<"Dati n : ";cin>>n; cout<<"Dati nr pe care trebuie sa-l cautam: ";cin>>x; for (i=0;i<n;i++) { cout<<"v["<<i+1<<"]=";cin>>v[i]; } i=1; while ( (i<=n) && (!gasit) ) { if (v[i]==x) gasit=1; i++; } if (gasit) cout<<x<<" se afla in vector"; else cout<<x<<" nu se afla in vector"; return 0;} |
Căutarea prin
metoda Divide et Impera – căutarea binară
O metodă care reduce mult mai mult complexitatea
operaţiei de căutare a unei valori val
într-un tablou v ordonat (crescător)
este metoda „divide et impera”, prin
care domeniul de valori în care se caută soluţia unei probleme este redus pas
cu pas (divide) până la găsirea soluţiei (impera).
Iniţial, se compară valoarea val cu valoarea unui element reper, anume cel din mijlocul
tabloului:
-
dacă valoarea căutată
este mai mare decât a elementului din mijloc, e clar că îl vom căuta printre
elementele aflate la dreapta acestuia; altfel, vom căuta la stânga lui;
-
căutarea la dreapta
sau la stânga o vom face la fel, alegând ca reper elementul din mijloc.
Ex:
Se consideră tabloul V cu valori ordonate crescător.
5
|
5
|
5
|
6
|
7
|
7
|
8 |
8
|
8
|
9
|
10
|
10
|
25
|
25
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
Valoarea
căutată este 10 (5 <
10 < 25).
Începem căutarea:
-
localizăm elementul de
reper pe poziţia 7;
-
comparăm valoarea
căutată cu valoarea din mijloc (10 > 8); rezultă că elementul căutata s-ar
putea afla la dreapta;
continuăm căutarea:
8
|
8
|
9
|
10
|
10
|
25
|
25
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
-
localizăm elementul
reper pe poziţia 11;
-
comparăm valoarea
căutată cu cea a elementului reper (10 = 10); rezultă că elementul căutat a
fost găsit pe poziţia 11 din doar două căutări.
Rationamentul metodei
Pentru scrierea
algoritmului de căutare, folosim următoarele notaţii:
- primul şi ultimul pentru adresa primului, respectiv, ultimului element din secvenţa
de valori în care se face, la un moment dat, căutarea.
În exemplul nostru, la prima căutare, primul=1 şi ultimul=14; la a doua căutare, primul=8 şi ultimul=14;
- m pentru adresa elementului din
mijlocul secvenţei în care se face căutarea:
mij=(primul+ultimul) div 2
În exemplul nostru, la prima căutare, m=(1+14)
div 2 = 7, iar la a doua căutare, mij=(8+14) div 2=11.
Iniţial, primul şi ultimul au valorile 1,
respective 14. După ce se compară
valoarea căutată cu valoarea elementului din mijloc (mij), dacă valoarea căutată este la dreapta lui mij, atunci primul devine mij+1; dacă valoarea căutată este la
dreapta lui mij, atunci ultimul devine mij-1.
Secvenţa de valori în care se face căutarea este delimitată de adresele primul şi ultimul. Căutarea area sens doar dacă primul<ultimul. Dacă se ajunge la situaţia primul>ultimul,
valoarea căutată nu există în secvenţă şi se afişează mesajul corespunzător.
Raţionamentul descries se aplică doar dacă valoarea căutată se află printer
elementele vectorului. De aceea, întâi se compară valoarea căutată cu primul,
respective ultimul element din vector.
Dacă valoarea căutată se poate afla în vector, se intră în secvenţa
căutărilor prin înjumătăţire (căutare
binară).
Metoda căutării rapide prin înjumătăţiri succesive s. n. căutare binară şi foloseşte tehnica
cuceritorului Divide et Impera (Dezbină şi stăpâneşte).
1. Divide et Impera este o tehnică de rezolvare a problemelor prin descompunere în probleme din ce în ce mai simple, până la o problemă cu soluţie imediată – soluţie parţială. Soluţia problemei iniţiale se formează prin compunerea soluţiilor parţiale.
2. Căutarea binară foloseşte metoda Divide et Impera. Problema iniţială – căutarea unei valori întrun tablou ordonat – este descompusă în probleme de acelaşi fel, dar din ce în ce mai simple, prin reducerea, până la un singur element, a intervalului de valori în care se face căutarea.
1. Divide et Impera este o tehnică de rezolvare a problemelor prin descompunere în probleme din ce în ce mai simple, până la o problemă cu soluţie imediată – soluţie parţială. Soluţia problemei iniţiale se formează prin compunerea soluţiilor parţiale.
2. Căutarea binară foloseşte metoda Divide et Impera. Problema iniţială – căutarea unei valori întrun tablou ordonat – este descompusă în probleme de acelaşi fel, dar din ce în ce mai simple, prin reducerea, până la un singur element, a intervalului de valori în care se face căutarea.
2. Reprezentarea
algoritmului
   început căutare_binară
citeşte X //valoare
căutată
dacă (val >= V[1]) şi (val<=V[N])
atunci
primul=1
ultimul=n
mij=(primul+ultimul)/2
repetă
 mß(p+u) div 2
dacă val=V[m]
atunci
găsit=1
altfel
dacă val > V[m]
atunci
pßm+1;
altfel
ußm-1;
sfârşit dacă
sfârşit dacă
până când (găsit=1) sau (p>u)
dacă găsit=0
atunci scrie „valoare inexistentă”
altfel scrie „valoarea a fost găsită în poziţia” p
sfârşit dacă
altfel
scrie „valoare inexistentă”
sfârşit dacă
sfârşit căutare_binară
|
Cautarea binara se bazeaza pe tehnica de programare Divide et Impera. Elementul cautat este “verificat” cu mijlocul vectorului. Daca elementul este egal cu mijlocul,cautarea se termina. Insa daca nu sunt egale, se compara valoarea mijlocului cu cea a elementului de cautat. Daca elementul este mai mare se continua cautarea de la mijlocul listei pana la sfarsit, iar daca este mai mic se continua cautarea de la inceput pana la mijloc.
| #include <iostream> using namespace std; int main() { int mij,n,i,x,v[100],primul,ultimul,gasit=0; cout<<"Dati n : ";cin>>n; cout<<"Introduceti elementele vectorului ordonate crescator \n"; for (i=1;i<=n;i++) {cout<<"v["<<i<<"]=";cin>>v[i];}//citire vector cout<<"Dati nr pe care trebuie sa-l cautam:"<<"x=";cin>>x; primul=1; ultimul=n; mij=(primul+ultimul)/2; while ( (primul<ultimul) && (!gasit) )// cautare valoarea x in vectorul ordonat crescator { if (v[mij]==x) {gasit=1;break;} else if (v[mij]<x) primul=mij+1; else if (v[mij]>x) ultimul=mij-1 } if (gasit) cout<<x<<" se afla in vector pe pozitia "<<mij; else cout<<x<<" nu se afla in vector"; return 0; } |
