# Algorisme de cerca

Un algorisme de cerca és un algorisme que està dissenyat per localitzar un element amb certes propietats dins d'una estructura de dades; per exemple, situar el registre corresponent a certa persona en una base de dades, o el millor moviment en una partida d'escacs.
La variant més simple del problema és la cerca d'un nombre en un vector.

## Cerca informada vs no informada

Un problema típic de la Intel·ligència Artificial consisteix a buscar un estat concret entre un conjunt determinat, al que se li crida espai d'estats. Imaginem, per exemple, una habitació amb rajoles en la qual hi ha un llibre. Un robot es desitja desplaçar per l'habitació amb la finalitat d'arribar a aquest llibre. De quina manera ho farà? En aquest punt és on entren en joc les estratègies i els algorismes de cerca.
Quan el sistema agent (en aquest cas, el robot) posseeix algun tipus d'informació del mitjà, s'utilitzen tècniques de cerques informades; no obstant això, si manca de coneixement algun, s'hauran d'utilitzar algorismes de cerca no informades. En el nostre exemple, i per a aquest últim cas, podem imaginar un robot que no posseeixi cap tipus de visió artificial, que únicament sigui capaç de moure's en horitzontal o vertical d'una rajola a un altre i detectar si a la rajola es troba el llibre.
D'aquesta forma, els algorismes de cerca poden ser:
* Algorismes no informats o cecs: en general més ineficients en temps i memòria que altres mètodes.
* Algorismes informats
** Algorismes heurístics: destaquen les Cerques Primer el Millor (Algorisme voraç o Greedy i Algorisme de cerca A) i de Millora Iterativa (Algorisme Escalada Simple -Hill Climbing- i Escalada per Màxima Pendent)
** Algorismes de Cerca amb adversari: destaquen el Minimax i el Poda alfa-beta.

## Cerca seqüencial

S'utilitza quan el vector no està ordenat o no pot ser ordenat prèviament. Consisteix a buscar l'element comparant-ho seqüencialment (d'aquí el seu nom) amb cada element del vector fins a trobar-ho, o fins que s'arribi al final. L'existència es pot assegurar quan l'element és localitzat, però no podem assegurar la no existència fins a no haver analitzat tots els elements del vector. A continuació es mostra el pseudocodi de l'algorisme:
* C
* int busquedaSimple(int vector[n], int n, int dato) { int i; for(i=0; i<n; i++){ if(dato==vector[i]) { return i; break; } } return -1; }

## Cerca dicotòmica (binària)

S'utilitza quan el vector en el qual volem determinar l'existència d'un element està prèviament ordenat. Aquest algorisme redueix el temps de cerca considerablement, ja que disminueix exponencialment el nombre d'iteracions necessàries. En el pitjor dels casos el nombre màxim de comparacions és ⌊log$_2$⁡n+1⌋{\textstyle \lfloor \log _{2}n+1\rfloor }és el nombre dels elements en el vector. Per exemple, en un contenint 50.000.000 elements, l'algorisme realitza com a màxim 26 comparacions. Per implementar aquest algorisme es compara l'element a buscar amb un element qualsevol del vector (normalment l'element central): si el valor d'aquest és major que el de l'element buscat es repeteix el procediment en la part del vector que va des de l'inici d'aquest fins a l'element pres, en cas contrari es pren la part del vector que va des de l'element pres fins al final. D'aquesta manera obtenim intervals cada vegada més petits, fins que s'obtingui un interval indivisible. Si l'element no es troba dins d'aquest últim llavors es dedueix que l'element buscat no es troba en tot el vector.$$$$$$$$$$$$$$$$$$$$$$$$A continuació es presenta el pseudocodi de l'algorisme, prenent com a element inicial l'element central del vector.
* C

### Implementació recursiva en C++

* C++

### Implementació recursiva en Python

* Python

### Implementació recursiva en Python3

* Python

### def bin(a,x,low,hi): ans = -1 if low==hi: ans = -1 else: mid = (low+((hi-low)//2)) if x < a[mid]: ans = bin(a,x,low,mid) elif x > a[mid]: ans = bin(a,x,mid+1,hi) else: ans = mid return ans # És crida amb: print(bin(Lista, numero_a_buscar, 0, len(Lista))) # Retorna l'índex que coincideix amb 'numero_a_buscar', si no retorna -1 # Temps: (log n)
### Implementació iterativa en Python3

* Python

## Referències

* ↑ «¿Que es un algoritmo?». Arxivat de l'original el 2017-09-07. [Consulta: 29 maig 2017].

## Enllaços externs

* ALT: Algorithm Learning Tool. Eina de suport a l'ensenyament d'algorismes que mostra gràficament el seu funcionament. Permet implementar algorismes propis i realitzar una execució dinàmica i interactiva