Căutare binară

PROBLEMĂ:Se citeşte un vector cu n componente numere întregi, unde numerele se presupun ordonate crescător şi o valoare întreagă nr. Să se decidă dacă nr se găseşte sau nu printre numerele citite, iar în caz afirmativ să se tipărească indicele componentei care conţine acea valoare.

OBSERVAŢIE: O rezolvare în care valoarea variabilei nr se compară pe rând cu cele n valori, este lipsită de eficienţă (nu exploatează faptul că cele n valori sunt în secvenţă crescătoare). Algoritmul care va fi propus este mult mai performant şi se bazează pe faptul că elementele vectorului sunt ordonate.

1 7 11 15 21 28 30 41 50

Vectorul iniţial

Numărul căutat

50

1 7 11 15 21 28 30 41 50

i=1 j=9

Valoarea elementului de pe poziţia din mijloc este:

v[(i+j)/2]=21

Se verifică dacă numărul căutat este egal cu valoarea din şir aflată pe poziţia din mijloc

50=21? FALS

28 30 41 50

i=6 j=9

Se reia algoritmul

v[(i+j)/2]=30

50=30? FALS atunci

50<30? FALS

Se compară numărul căutat cu elmentul aflat pe poziţia din mijloc

50<21? FALS, atunci

căutarea se face în jumătatea a doua a şirului

41 50

i=8 j=9

v[(i+j)/2]=41

50=41? FALS atunci

50<41? FALS

50

v[(i+j)/2]=50

50=50? ADEVĂRAT

Numărul căutat se află pe poziţia 9

i=9 j=9

#include<iostream.h>int v[100], n, nr;void caut (int i, int j){if (nr==v[(i+j)/2])cout<<“gasit”<<“ “<<“indice”<<(i+j)/2;elseif (i<j)if (nr<v[(i+j)/ 2])caut (i, (i+j)/2 -1);else caut ((i+j)/2 +1, j);};main(){cout<<“n=“; cin>>n;for (int i=1; i<=n; i++){cout<<“v[“<<i<<“]=“; cin>>v[i];cout<<“nr=“; cin>>nr;caut (1,n);}

Algoritmul de căutare binară efectuează cel mult [ ]+1 comparaţii, în cazul unei căutări cu succes, respectiv [ ] sau [ ]+1 comparaţii, în cazul unei căutări fără succes, unde n este dimensiunea spaţiului de căutare.

Performanţă

n2logn2log

n2log