Content

• Gràfic de comparació
• Definició de Lineal Search
• Definició de cerca binària
• Conclusió

La recerca lineal i la cerca binària són els dos mètodes que s'utilitzen en matrius de cercant els elements. La cerca és un procés de cerca d’un element dins de la llista d’elements emmagatzemats en qualsevol ordre o aleatòriament.

La diferència principal entre la cerca lineal i la cerca binària és que la cerca binària requereix menys temps per cercar un element de la llista d’elements ordenada. Per tant, es dedueix que l’eficiència del mètode de cerca binària és més gran que la cerca lineal.

Una altra diferència entre ambdues és que hi ha un requisit previ per a la cerca binària, és a dir, els elements han de ser ordenats mentre que a la cerca lineal no hi ha cap requisit previ. Tot i que els dos mètodes de cerca utilitzen tècniques diferents que es tracten a continuació.

1. Gràfic de comparació
2. Definició
3. Diferències claus
4. Conclusió

Gràfic de comparació

Bases per a la comparació	Recerca lineal	Recerca binària
Complexitat horària	O (N)	O (registre 2 N)
Millor cas	Primer Element O (1)	Element central O (1)
Prerequisit per a una matriu	No és necessari	La matriu ha d’estar ordenada
Pitjor cas per N nombre d’elements	N calen comparacions	Es pot concloure després del registre2N comparacions
Es pot implementar el	Llista Matriu i enllaç	No es pot implementar directament a la llista enllaçada
Operació d'inserció	S'insereix fàcilment al final de la llista	Cal que el processament s'insereixi al lloc adequat per mantenir una llista ordenada.
Tipus d'algoritme	Iteratiu de naturalesa	Divideix i conquereix en la natura
Utilitat	Fàcil d'utilitzar i no necessita cap element ordenat.	Alguns algoritmes i elements complicats haurien d’estar organitzats en ordre.
Línies de codi	Menys	Més

Definició de Lineal Search

En una cerca lineal, cada element d'una matriu es recupera un per un en un ordre lògic i es comprova si és l'element desitjat o no. Si no s’accedeix a tots els elements i no es troba l’element desitjat, una cerca no reeixirà. En el pitjor dels casos, és possible que hàgim d’escanejar la meitat de la mida de la matriu (n / 2).

Per tant, la cerca lineal es pot definir com la tècnica que recorre la matriu de forma seqüencial per localitzar l'element donat. El programa que es mostra a continuació il·lustra la cerca d’un element de la matriu mitjançant la cerca.

Eficiència de cerca lineal

L’eficiència de la tècnica determina el consum de temps o el nombre de comparacions realitzades per cercar un registre en una taula de cerca. Si el registre desitjat es troba a la primera posició de la taula de cerca, només es farà una comparació. Quan el registre desitjat és l’últim, caldrà fer n comparacions. Si el registre es presenta en algun lloc de la taula de cerca, de mitjana, el nombre de comparacions serà (n + 1/2). La pitjor eficiència dels casos d'aquesta tècnica és que O (n) significa l'ordre d'execució.

Programa C per cercar un element amb tècnica de cerca lineal.

#incloure #incloure void main () {int a, n, i, item, loc = -1; clrscr (); f (" nEntreu el nombre d'elements:"); scanf ("% d", & n); f ("Introduïu els números: n"); per (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" n Introduïu el número que cal cercar:"); scanf ("% d", & element); per (i = 0; i <= n-1; i ++) {if (ítem == a) {loc = i; trencar; }} if (loc> = 0) {f (" n% d es troba a la posició% d:", element, loc + 1); } else {f (" n L'element no existeix"); } getch (); }

Definició de cerca binària

La cerca binària és un algoritme extremadament eficient. Aquesta tècnica de cerca consumeix menys temps per cercar l’element donat en mínimes comparacions possibles. Per fer la cerca binària, primer hem d’ordenar els elements de la matriu.

A continuació, es mostra la lògica d'aquesta tècnica:

• Primer, busqueu l’element mig de la matriu.
• L’element mig de la matriu es compara amb l’element que s’ha de cercar.

Hi poden haver tres casos:

1. Si l’element és l’element obligatori, la cerca té èxit.
2. Quan l’element sigui inferior a l’element desitjat, només busqueu la primera meitat de la matriu.
3. Si és superior a l'element desitjat, cerqueu a la segona meitat de la matriu.

Repetiu els mateixos passos fins que un element no es trobi o s’esgoti a l’àrea de cerca. En aquest algorisme, cada àrea de cerca es redueix. Per tant, el nombre de comparacions és, com a màxim, log (N + 1). Com a resultat, és un algorisme eficient en comparació amb la cerca lineal, però la matriu s'ha d'ordenar abans de fer la cerca binària.

Programa C per trobar un element amb tècnica de cerca binària.

#incloure void main () {int i, suplicar, acabar, mig, n, cercar, matriu; f ("Introduïu el nombre d'element n"); scanf ("% d", & n); f ("Introduïu els% d números n", n); per a (i = 0; i <n; i ++) scanf ("% d", i matriu); f ("Introduïu el número que cal cercar n"); scanf ("% d", i cerca); suplicar = 0; final = n - 1; mig = (suplicar + final) / 2; while (beg <= end) {if (array <cerca) beg = middle + 1; else if (array == search) {f ("La cerca té èxit. n% d es troba a la ubicació% d. n", a la cerca, al centre + 1); trencar; } else end = mig - 1; mig = (suplicar + final) / 2; } if (beg> end) f ("La cerca no té èxit!% d no està present a la llista. n", cerca); getch (); }

1. La cerca lineal té caràcter iteratiu i utilitza enfocament seqüencial. D'altra banda, la cerca binària implementa solucions de divisió i conquesta.
2. La complexitat temporal de la cerca lineal és O (N) mentre que la cerca binària té O (log₂N).
3. El millor cas per a la cerca lineal és el primer element, és a dir, O (1). En contraposició, a la cerca binària és per a l'element mig, és a dir, O (1).
4. En la cerca lineal, el pitjor dels casos per cercar un element és el nombre de comparació. En canvi, és registre₂Nombre de comparacions per a la cerca binària.
5. La cerca lineal es pot implementar tant en una matriu com en una llista enllaçada mentre que la cerca binària no es pot implementar directament a la llista enllaçada.
6. Com sabem, la cerca binària requereix la matriu ordenada i que és la raó. Es requereix que el processament s'insereixi en el seu lloc adequat per mantenir una llista ordenada. Per contra, la cerca lineal no requereix elements ordenats, de manera que els elements s’insereixen fàcilment al final de la llista.
7. La cerca lineal és fàcil d’utilitzar i no cal cap element ordenat. D'altra banda, l'algoritme de cerca binària és tan complicat, i els elements estan necessàriament ordenats en ordre.

Conclusió

Tant els algorismes de cerca lineals com binaris poden ser útils depenent de l'aplicació. Quan una matriu és l'estructura de dades i els elements estan ordenats en ordre ordenat, es preferirà la cerca binària ràpidcercant. Si la llista enllaçada és l’estructura de dades independentment de com s’organitzin els elements, s’adopta la cerca lineal a causa de la indisponibilitat d’implementació directa de l’algorisme de cerca binària.

El típic algorisme de cerca binària no es pot utilitzar per a la llista enllaçada, perquè la llista enllaçada és de naturalesa dinàmica i no se sap on s'assigna realment l'element mig. Per tant, hi ha un requisit de dissenyar la variació de l'algorisme de cerca binària que pot funcionar també a la llista enllaçada, ja que la cerca binària té una execució més ràpida que una cerca lineal.