La cerca binària és una de les maneres més fàcils de trobar un element en una matriu

Molt sovint, els programadors, fins i tot els principiants, s'enfronten al fet que hi ha un conjunt de números en què cal trobar un nombre determinat. Aquesta col · lecció s'anomena matriu. I per trobar l'element correcte en ell, hi ha moltes maneres. Però el més simple entre ells és la cerca binària. Quin és el mètode? I com implementar una cerca binària? Pascal és l'entorn més senzill per organitzar aquest programa, per la qual cosa el farem servir per a l'estudi.

En primer lloc, analitzarem quins són els avantatges d'aquest mètode, després de tot, de manera que podem comprendre, Quin és el punt d'estudi d'aquest tema. Per tant, suposem que hi ha una matriu amb una dimensió d'almenys 100000000 elements, en els quals heu de trobar un específic. Per descomptat, aquest problema es pot resoldre fàcilment mitjançant una simple cerca lineal, en què utilitzem un bucle per comparar l'element desitjat amb tots els que existeixen en la matriu. El problema és que la implementació d'aquesta idea trigarà massa temps. En un programa senzill de Pascal per a diversos procediments i amb tres línies del text principal, no ho notaràs, però quan inicieu projectes més o menys grans amb una gran quantitat de branques i una bona funcionalitat, el programa final es carregarà massa temps. Sobretot si l'equip té un rendiment deficient. Per tant, hi ha una cerca binària, que redueix el temps de cerca almenys dues vegades.

Quin és el principi d'aquest mètode? Immediatament val la pena dir que la recerca binària no funciona en cap matriu, sinó només en un conjunt ordenat de nombres. En cada pas següent, es pren l'element mitjà de la matriu (referint-se al número de l'element). Si el nombre desitjat és superior a la mitjana, tot el que queda a l'esquerra, és a dir, menys que l'element mitjà, es pot descartar i no cercar-hi. A la inversa, si és inferior a la mitjana, entre els números de la dreta, no els podeu buscar. A continuació, seleccionarem una nova àrea de cerca, on l'element mig de tota la matriu serà el primer element i l'últim serà l'últim. El nombre mitjà de la nova àrea serà ¼ de tot el segment, és a dir (l'últim element + l'element mitjà de tota la matriu) / 2. Una vegada més, es realitza la mateixa operació: la comparació amb la mitjana de la matriu. Si el valor desitjat és inferior a la mitjana, descarteu el costat dret i feu el mateix fins que es trobi aquest element mig.

Per descomptat, la millor manera de veure l'exemple és com escriure una cerca binària. Pascal aquí és adequat per a tothom: la versió no és important. Anem a escriure un programa senzill.

Tindrà una matriu d'1 a h anomenada "massiva", una variable que indica un límit inferior de cerca, anomenat "niz", un límit superior anomenat "verh", l'element de cerca central és "sredn"; I el número requerit és "isk".

Per tant, primer assigni els límits superior i inferior de l'interval de cerca:

Niz: = 1;
Verh: = h + 1;

A continuació, organitzem el cicle "mentre que el fons és inferior al límit superior":

Tot i que no Comença

A cada pas, divideix el segment en 2:

Sredn: = (niz + verh) div 2; {Utilitzeu la funció div perquè dividim la resta}

Cada vegada que realitzem un xec. Si la mitjana és igual a la desitjada, interrompem el cicle, ja que ja es troba l'element desitjat:

Si sredn = isk llavors es trenca;

Si l'element mig de la matriu és més gran que el que estem buscant, descartem el costat esquerre, és a dir, assignem l'element mig al límit superior:

Si massiv [sredn]> isk then verh: = sredn;

I si, pel contrari, el converteixen en el límit inferior:

Else niz: = sredn;
Final;

Això és tot el que hi haurà al programa.

Anem a analitzar com es veurà el mètode binari en la pràctica. Preneu aquesta matriu: 1, 3, 5, 7, 10, 12, 18 i cerqueu el número 12 en ell.

En total, tenim 7 elements, de manera que la mitjana serà la quarta, el seu valor 7.

Ja que 12 són majors de 7, els elements 1, 3 i 5 es poden descartar. A continuació, tenim 4 números a la izquierda, 4/2 sense restants 2. És així que el nou element mig serà de 10.

Des de les 12 són més de 10, descartem 7. Només queden 10, 12 i 18.

Aquí l'element mig ja és de 12, aquest és el nombre necessari. S'ha completat la tasca: es troba el número 12.