Abans d'entendre les diferències entre la cerca lineal i la binària, primer hauríem de conèixer la cerca lineal i la cerca binària per separat.
Què és una cerca lineal?
Una cerca lineal també es coneix com a cerca seqüencial que simplement escaneja cada element alhora. Suposem que volem cercar un element en una matriu o llista; simplement calculem la seva longitud i no saltem cap a cap element.
Considerem un exemple senzill.
Suposem que tenim una matriu de 10 elements com es mostra a la figura següent:
La figura anterior mostra una matriu de tipus de caràcter que té 10 valors. Si volem cercar 'E', aleshores la cerca comença des del 0thelement i escaneja cada element fins que no es trobi l'element, és a dir, 'E'. No podem saltar directament del 0thelement al 4thelement, és a dir, cada element s'escaneja un per un fins que no es troba l'element.
Complexitat de la cerca lineal
Com a cerca lineal, escaneja cada element un per un fins que no es troba l'element. Si augmenta el nombre d'elements, també augmenta el nombre d'elements a escanejar. Podem dir que el El temps necessari per buscar els elements és proporcional al nombre d'elements . Per tant, la complexitat del pitjor dels casos és O(n)
Què és una cerca binària?
Una cerca binària és una cerca en la qual es calcula l'element central per comprovar si és més petit o més gran que l'element que s'ha de cercar. El principal avantatge d'utilitzar la cerca binària és que no escaneja tots els elements de la llista. En lloc d'escanejar cada element, realitza la cerca a la meitat de la llista. Per tant, la cerca binària triga menys temps a cercar un element en comparació amb una cerca lineal.
L'únic requisit previ per a la cerca binària és que una matriu hauria d'estar ordenada, mentre que la cerca lineal funciona tant en matriu ordenada com no ordenada. L'algorisme de cerca binària es basa en la tècnica de dividir i conquerir, el que significa que dividirà la matriu de manera recursiva.
Hi ha tres casos utilitzats en la cerca binària:
Cas 1: dades
Cas 2: dades>a[mitjana] i després dreta=mitjana-1
Cas 3: dades = a[mid] // es troba l'element
En el cas anterior, ' a ' és el nom de la matriu, mig és l'índex de l'element calculat recursivament, dades és l'element que s'ha de cercar, esquerra denota l'element esquerre de la matriu i dret denota l'element que es produeix al costat dret de la matriu.
Entendrem el funcionament de la cerca binària a través d'un exemple.
Suposem que tenim una matriu de mida 10 que està indexada de 0 a 9, tal com es mostra a la figura següent:
Volem cercar 70 elements de la matriu anterior.
Pas 1: Primer, calculem l'element central d'una matriu. Considerem dues variables, és a dir, l'esquerra i la dreta. Inicialment, esquerra = 0 i dreta = 9 tal com es mostra a la figura següent:
El valor de l'element mitjà es pot calcular com:
Per tant, mid = 4 i a[mid] = 50. L'element a cercar és 70, per tant a[mid] no és igual a les dades. Es compleix el cas 2, és a dir, data>a[mid].
Pas 2: Com a dades>a[mid], el valor de left s'incrementa a mitjan+1, és a dir, left=mid+1. El valor de mid és 4, de manera que el valor de left es converteix en 5. Ara, tenim un subbarray tal com es mostra a la figura següent:
Ara, de nou, el valor mitjà es calcula utilitzant la fórmula anterior i el valor de mig es converteix en 7. Ara, el valor mitjà es pot representar com:
A la figura anterior, podem observar que a[mid]>data, de manera que de nou, el valor de mid es calcularà en el següent pas.
Pas 3: Com a [mid]>data, el valor de right es disminueix a mitjan 1. El valor de mid és 7, de manera que el valor de right es converteix en 6. La matriu es pot representar com:
El valor de mid es tornarà a calcular. Els valors d'esquerra i dreta són 5 i 6, respectivament. Per tant, el valor de mid és 5. Ara el mid es pot representar en una matriu tal com es mostra a continuació:
A la figura anterior, podem observar que una[mitjana]
Pas 4: Com a [mitjana] Ara el valor de mid es torna a calcular utilitzant la fórmula que ja hem comentat. Els valors de l'esquerra i la dreta són 6 i 6 respectivament, de manera que el valor de mid es converteix en 6 tal com es mostra a la figura següent: Podem observar a la figura anterior que a[mid]=data. Per tant, la cerca s'ha completat i l'element es troba correctament. A continuació es mostren les diferències entre la cerca lineal i la cerca binària: Descripció La cerca lineal és una cerca que troba un element a la llista cercant l'element seqüencialment fins que l'element es troba a la llista. D'altra banda, una cerca binària és una cerca que troba l'element central de la llista de forma recursiva fins que l'element central coincideix amb un element cercat. Funcionament de les dues cerques La cerca lineal comença a buscar des del primer element i escaneja un element a la vegada sense saltar al següent element. D'altra banda, la cerca binària divideix la matriu a la meitat calculant l'element central d'una matriu. Implementació La cerca lineal es pot implementar en qualsevol estructura de dades lineal, com ara vector, llista enllaçada individualment, llista enllaçada doble. En canvi, la cerca binària es pot implementar en aquelles estructures de dades amb un recorregut bidireccional, és a dir, un recorregut cap endavant i cap enrere. Complexitat La cerca lineal és fàcil d'utilitzar, o podem dir que és menys complexa ja que els elements per a una cerca lineal es poden disposar en qualsevol ordre, mentre que en una cerca binària, els elements s'han d'ordenar en un ordre particular. Elements ordenats Els elements per a una cerca lineal es poden ordenar en ordre aleatori. No és obligatori en la cerca lineal que els elements estiguin ordenats. D'altra banda, en una cerca binària, els elements s'han d'ordenar ordenats. Es pot organitzar en ordre creixent o decreixent i, en conseqüència, es canviarà l'algorisme. Com que la cerca binària utilitza una matriu ordenada, cal inserir l'element al lloc adequat. En canvi, la cerca lineal no necessita una matriu ordenada, de manera que el nou element es pot inserir fàcilment al final de la matriu. Aproximació La cerca lineal utilitza un enfocament iteratiu per trobar l'element, per la qual cosa també es coneix com a enfocament seqüencial. En canvi, la cerca binària calcula l'element central de la matriu, de manera que utilitza l'enfocament de dividir i conquerir. Conjunt de dades La cerca lineal no és adequada per al conjunt de dades gran. Si volem cercar l'element, que és l'últim element de la matriu, una cerca lineal començarà a buscar des del primer element i continuarà fins a l'últim element, de manera que el temps necessari per cercar l'element seria gran. D'altra banda, la cerca binària és adequada per a un conjunt de dades gran, ja que triga menys temps. Velocitat Si el conjunt de dades és gran en la cerca lineal, el cost computacional seria alt i la velocitat es torna lenta. Si el conjunt de dades és gran a la cerca binària, el cost computacional seria menor en comparació amb una cerca lineal i la velocitat esdevé ràpida. Dimensions La cerca lineal es pot utilitzar tant en matriu simple com multidimensional, mentre que la cerca binària només es pot implementar en matriu unidimensional. Eficiència La cerca lineal és menys eficient si tenim en compte els grans conjunts de dades. La cerca binària és més eficient que la cerca lineal en el cas de grans conjunts de dades. Vegem les diferències en forma tabular. 
Diferències entre la cerca lineal i la cerca binària
substituïu la cadena a la cadena java
Base de comparació Cerca lineal Cerca binària Definició La cerca lineal comença a buscar des del primer element i compara cada element amb un element cercat fins que l'element no es troba. Troba la posició de l'element cercat trobant l'element central de la matriu. Dades ordenades En una cerca lineal, els elements no cal que estiguin ordenats. La condició prèvia per a la cerca binària és que els elements s'han d'ordenar en un ordre ordenat. Implementació La cerca lineal es pot implementar en qualsevol estructura de dades lineal, com ara una matriu, una llista enllaçada, etc. La implementació de la cerca binària és limitada, ja que només es pot implementar en aquelles estructures de dades que tenen un recorregut bidireccional. Aproximació Es basa en l'enfocament seqüencial. Es basa en l'enfocament divideix i vencem. Mida És preferible per als conjunts de dades de mida petita. És preferible per als conjunts de dades de gran mida. Eficiència És menys eficient en el cas de conjunts de dades de gran mida. És més eficient en el cas de conjunts de dades de gran mida. En el pitjor dels casos En una cerca lineal, el pitjor dels casos per trobar l'element és O(n). En una cerca binària, el pitjor dels casos per trobar l'element és O (log2n). El millor dels casos En una cerca lineal, el millor escenari per trobar el primer element de la llista és O(1). En una cerca binària, el millor dels casos per trobar el primer element de la llista és O(1). Matriu dimensional Es pot implementar tant en una matriu única com multidimensional. Només es pot implementar en una matriu multidimensional.