Algorithmo de recerca

De Wikipedia, le encyclopedia libere
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]

Articulo principal: Recerca 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[modificar | modificar fonte]

Nota
Nota