Cerca binària vs cerca lineal
La cerca lineal, també coneguda com a cerca seqüencial, és l'algorisme de cerca més senzill. Cerca un valor especificat en una llista comprovant tots els elements de la llista. La cerca binària també és un mètode utilitzat per localitzar un valor especificat en una llista ordenada. El mètode de cerca binari redueix a la meitat el nombre d'elements comprovats (en cada iteració), reduint el temps necessari per localitzar l'element donat a la llista.
Què és la cerca lineal?
La cerca lineal és el mètode de cerca més senzill, que comprova cada element d'una llista seqüencialment fins que troba un element especificat. L'entrada al mètode de cerca lineal és una seqüència (com ara una matriu, una col·lecció o una cadena) i l'element que cal cercar. La sortida és true si l'element especificat es troba dins de la seqüència proporcionada o fals si no és a la seqüència. Com que aquest mètode comprova tots els elements de la llista fins que es troba l'element especificat, en el pitjor dels casos passarà per tots els elements de la llista abans de trobar l'element requerit. La complexitat de la cerca lineal és o(n). Per tant, es considera que és massa lent per utilitzar-lo quan es cerquen elements en llistes grans. Però això és molt senzill i més fàcil d'implementar.
Què és la cerca binària?
La cerca binària també és un mètode utilitzat per localitzar un element específic en una llista ordenada. Aquest mètode comença comparant l'element cercat amb els elements del centre de la llista. Si la comparació determina que els dos elements són iguals, el mètode s'atura i retorna la posició de l'element. Si l'element cercat és més gran que l'element central, torna a iniciar el mètode utilitzant només la meitat inferior de la llista ordenada. Si l'element cercat és inferior a l'element central, torna a iniciar el mètode utilitzant només la meitat superior de la llista ordenada. Si l'element cercat no es troba dins de la llista, el mètode retornarà un valor únic que ho indica. Per tant, el mètode de cerca binària redueix a la meitat el nombre d'elements comparats (en cada iteració), en funció del resultat de la comparació. En conseqüència, la cerca binària s'executa en temps logarítmic, donant lloc a un rendiment mitjà de casos o(log n).
Quina diferència hi ha entre la cerca binària i la cerca lineal?
Tot i que tant la cerca lineal com la binària són mètodes de cerca, tenen diverses diferències. Mentre que la cerca binària funciona en llistes ordenades, la cerca de línia també pot operar en llistes no ordenades. L'ordenació d'una llista generalment té una complexitat mitjana de casos de n log n. La cerca lineal és senzilla i senzilla d'implementar que la cerca binària. Però, la cerca lineal és massa lenta per utilitzar-la amb llistes grans a causa del seu rendiment mitjà de casos o (n). D' altra banda, es considera que la cerca binària és un mètode més eficient que es podria utilitzar amb llistes grans. Però implementar la cerca binària podria ser bastant complicat i un estudi ha demostrat que el codi precís per a la cerca binària només es pot trobar en cinc de cada vint llibres.
