Algorithmo de recerca

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 
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) 

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 
 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 

Categoria:Algorithmos de recerca