Algorithmo de recerca

De Wikipedia, le encyclopedia libere
Saltar a: navigation, cercar

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 se arriva al fin. On pote fixar le existentia quando le elemento es localisate, ma non nos pote fixar le non existentia usque non haber analysate tote le elementos del arrangiamento. A continuation se monstra le pseudocodice del algorithmo:

Datos de entrata:
  vec: vector in le que on vole cercar le dato  
  tam: mesura del vector. Le subindices valide vade desde 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 dychotomic (binari)[modificar | modificar fonte]

(Vide plus: Recerca binari) On utilisa lo 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 arrays de grande mesura. Per exemplo, in un continente 50.000.000 elementos, realisa como maximo 26 comparationes (in le pejor del casos).

Pro implementar iste algorithmo on compara le elemento a cercar con un elemento qualcunque del array (normalmente le elemento central): si le valor de isto es major que le del elemento cercate le procedimento se repete in le parte del array que va desde le initio de isto usque le elemento prendite, in caso contrari on prende le parte del array que va desde 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 alora on deduce que le elemento cercate non se trova in tote le array.

A continuation presenta le pseudocodice del algorithmo, prendente como elemento initial le elemento central del array, es presentate.

Datos de entrata:
  vec: vector in le qual on vole cercar le dato
  tam: mesura del vector. Le subindices valide vade desde 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]

Logo

Iste pagina usa contento del Wikipedia in espaniol. Le articulo original se trova a es:Algoritmo de búsqueda, e es usate secundo le mandatos del licentia de Wikipedia.