Algorithmo de recerca
| Algorithmo de recerca |
|---|
| subclasse de: algorithmo, information retrieval[*] |
|
|
| Commons: Search algorithms |
Un algorithmo de recerca es un algorithmo que es designate pro localisar un elemento con certe proprietates intra un structura de datos; per exemplo, trovar le registro correspondente a certe persona in un base de datos, o le melior movimento in un partita de chacos.
Le variante plus simple del problema es le recerca de un numero in un vector.
Recerca sequential
[modificar | modificar fonte]On lo utilisa quando le vector non se trova ordinate o non pote esser ordinate previemente. Illo consiste in cercar le elemento comparante lo sequentialmente (de ibi su nomine) con cata elemento del arrangiamento usque trovar lo, o usque que illo arriva al fin. On pote fixar le existentia quando le elemento es localisate, sed nos non pote fixar le non existentia sin haber analysate tote le elementos del arrangiamento. Infra es monstrate le pseudocodice del algorithmo:
Datos de entrata: vec: vector in que on vole cercar le dato tam: mesura del vector. Le subindices valide va de 0 usque tam-1 inclusive. dato: elemento que on vole cercar. Variabiles pos: position actual in le arrangiamento pos = 0 durante_que pos < tam: Si vec[pos] == dato retornar ver e/o pos, alteremente: pos = pos + 1 Fin (durante_que) Retornar false,
Recerca dichotomic (binari)
[modificar | modificar fonte]On lo utilisa quando le vector, in le qual on vole determinar le existentia de un elemento, se trova previemente ordinate. Iste algorithmo reduce le tempore de recerca considerabilemente, durante que diminue exponentialmente le numero de iterationes necessari.
Illo es altemente recommendate pro cercar in arrangiamentos de grande mesura. Per exemplo, in un arragiamento continente 50.000.000 elementos, illo realisa al maximo 26 comparationes (in le pejor del casos).
Pro implementar iste algorithmo on compara le elemento a cercar con un elemento qualcunque del arragiamento (normalmente le elemento central): si le valor de isto es major que lo del elemento cercate le procedimento se repete in le parte del arragiamento que va ab le initio de isto usque le elemento prendite, in caso contrari on prende le parte del arragiamento que va ab le elemento prendite usque le fin. De iste maniera on obtene intervallos cata vice plus parve, usque que on obtene un intervallo indivisible. Si le elemento non se trova intra iste ultime intervallo alora on deduce que le elemento cercate non se trova in tote le arragiamento.
Infra es presentate le pseudocodice del algorithmo, prendente como elemento initial le elemento central del arragiamento.
Datos de entrata: vec: vector in le qual on vole cercar le dato tam: mesura del vector. Le subindices valide va de 0 usque tam-1 inclusive. dato: elemento que on vole cercar. Variabiles centro: subindice central del intervallo inf: limite inferior del intervallo sup: limite superior del intervallo inf = 0 sup = tam-1
durante_que inf <= sup:
centro = ((sup - inf) / 2) + inf // Division integre: se trunca le fraction
Si vec[centro] == dato retornar ver e/o pos, alteremente:
Si dato < vec[centro] alora:
sup = centro - 1
In caso contrari:
inf = centro + 1
Fin (durante_que)
Retornar false
- Implementation recursive in C++
#include <iostream> #include <vector>
bool recerca_dychotomic(const vector<int> &v, int principio, int fin, int &x){
bool res;
if(principio <= fin){
int m = (principio + fin)/2;
if(x < v[m]) res = recerca_dychotomic(v, principio, m-1, x);
else if(x > v[m]) res = recerca_dychotomic(v, m+1, fin, x);
else res = true;
}else res = false;
return res;
}
/*{Post: Si se trova, illo retorna true, si non - false}*/
Ligamines externe
[modificar | modificar fonte]- ALT: Algorithm Learning Tool. Utensile de appoio al inseniamento de algorithmos que monstra graphicamente su functionamento. Permitte implementar algorithmos proprie e realisar un execution dynamic e interactive Archived 2009-02-08 at the Wayback Machine
