Taula de continguts:
Definició: què significa la cerca binària?
S'utilitza un algorisme de cerca binària per trobar la posició d'un valor específic contingut en una matriu ordenada. Funcionant amb el principi de dividir i conquerir, aquest algorisme de cerca pot ser bastant ràpid, però és bàsic que les dades siguin de forma ordenada. Funciona iniciant la cerca al mig de la matriu i treballant baixant a la primera meitat inferior o superior de la seqüència. Si el valor mitjà és inferior al valor objectiu, això vol dir que la cerca ha de ser superior, si no, haureu de mirar la part descendent de la matriu.
Una cerca binària també es coneix com a cerca de mig interval o cerca logarítmica.
Techopedia explica la cerca binària
Una cerca binària és un mètode ràpid i eficient per trobar un valor objectiu específic d’un conjunt d’elements ordenats. En començar a la meitat de la llista ordenada, pot reduir de manera efectiva l'espai de cerca a la meitat determinant si ascendeix o baixa la llista en funció del valor mitjà en comparació amb el valor objectiu.
Per exemple, amb un valor de destinació de 8 i un espai de cerca d’1 a 11:
- Es troba el valor mitjà / mitjà i s’hi estableix el punter, que en aquest cas és 6.
- El target de 8 es compara amb 6. Com que el 6 és menor de 8, l’objectiu ha d’estar a la meitat superior.
- El punter es mou al següent valor (7) i es compara amb la destinació. És més petit, per tant, el punter es mou al següent valor més alt.
- El punter està a 8. Comparat amb la destinació, es tracta d’una coincidència exacta, per tant l’objectiu s’ha trobat.
Mitjançant la cerca binària, només s’ha de comparar l’objectiu amb tres valors. En comparació de fer una cerca lineal, hauria començat des del primer valor i s’hauria elevat, necessitant comparar l’objectiu amb vuit valors. Una cerca binària només és possible amb un conjunt de dades ordenat; si les dades s’ordenen aleatòriament, una cerca lineal donaria resultats tot el temps mentre que una cerca binària probablement quedaria enganxada en un bucle infinit.
