Busca binaria

Busca binaria

En ciències de la computació i matemàtiques, la busca binaria, també coneguda, com a busca d'interval mig o busca logarítmica, és un algoritme de busca que troba la posició d'un valor en un array ordenat. Compara el valor en l'element en el mig del array, si no són iguals, la mitat en la qual el valor no pot estar és eliminada i la busca continua en la mitat restant fins que el valor es trobe.

La busca binaria és computada en el pijor dels casos en un temps logarítmic, realisant $O(\log n)$ comparacions, a on n és el número d'elements de l'apany i log és el logaritmo. La busca binaria requerix solament O(1) en espai, és dir, que l'espai requerit per l'algoritme és el mateix per a qualsevol cantitat d'elements en el array. Encara que estructures de senyes especialisades en la busca ràpides com les taules hash poden ser més eficients, la busca binaria s'aplica a un ampli ranc de problemes de busca.

Encara que l'idea és simple, implementar la busca binaria correctament requerix atenció a alguns detalls com la seua condició de parada i el càlcul del punt mig d'un interval.

Existixen numeroses variacions de la busca binaria. Una variació particular (cascada fraccional) accelera la busca binaria per a un mateix valor en múltiples apanys.

Algoritme

La busca binaria funciona en apanys ordenats. La busca binaria comença per comparar l'element del mig de l'apany en el valor buscat. Si el valor buscat és igual a l'element del mig, la seua posició en l'apany és retornada. Si el valor buscat és menor o major que l'element del mig, la busca contínua en la primera o segona mitat, respectivament, deixant l'atra mitat fòra de consideració.

Procediment

Donat un vector A de n elements en valors A₀ ... A_n−1, ordenats tal que A₀ ≤ ... ≤ A_n−1, i un valor buscat T, el següent procediment usa busca binaria per a trobar l'índex de T en A.

1. Assignar 0 a L i a R (n − 1).
2. Si L > R, la busca termina sense trobar el valor.
3. Siga m (la posició de l'element del mig) igual a la part sancera de (L + R) / 2.
4. Si A_m < T, igualar L a m + 1 i anar al pas 2.
5. Si A_m > T, igualar R a m – 1 i anar al pas 2.
6. Si A_m = T, la busca va terminar, retornar m.

Este procediment iterativo manté els llímits de la busca per mig de dos variables. Algunes implementacions realisen la comparació d'igualtat al final de l'algoritme, com resultant s'obté un cicle més ràpit de comparacions pero s'aumenta en un la cantitat de iteraciones promig.

Coincidències aproximades

El procediment anterior solament realisa coincidències exactes, trobant la posició del valor buscat. No obstant, donat l'orde natural dels apanys ordenats, és trivial estendre la busca binaria per a realisar coincidències aproximades. Per eixemple, la busca binaria pot ser usada per a computar, per a un valor donat, el seu rank (el número d'elements menors), antecessor (pròxim element menor), successor (pròxim element major), i veïns propencs. Les consultes en intervals, com per eixemple, buscar el número d'elements entre dos números poden ser computades en dos preguntes de rank.

• Les consultes de rank poden ser realisades usant una modificació de la busca binaria, retornant m en les busques a on es trobe l'element, i L en a on no es trobe, corresponent este últim al número d'elements menors que el valor buscat.

• Les consultes d'antecessor i successor poden ser computades en preguntes de rank també. Una volta que el rank del valor buscat és conegut, el seu antecessor és l'element en la posició donat per la seua rank(l'element major que és menor que el valor buscat). El seu successor és l'element despuix del (si ell està present en l'apany) o en la posició següent a l'antecessor (en un atre cas). El veí més propenc del valor buscat és el seu antecessor o el seu successor, dels dos el més propenc.
• Les consultes de ranc són també fàcils de manipular. Una volta que els rank d'abdós valors són coneguts, el número d'elements majors o iguals al primer valor i menors que el segon és la diferència dels dos ranks. Esta cantitat pot disminuir o aumentar d'acort si els extrems de l'interval deuen ser considerats part de la pregunta en qüestió i quan l'apany continga claus que coincidixquen en els extrems.

Rendiment

Un arbre que representa l'algoritme de busca binaria. L'apany en el qual s'usa l'algoritmes és [20, 30, 40, 50, 90, 100], i el valor buscat és 40.

El rendiment de la busca binaria pot ser analisada reduint l'algoritme a un arbre binario de busca, a on la raïl és l'element en el mig de l'apany, l'element en el mig de la primera part de l'apany és el fill esquerre de la raïl i l'element en el mig de la segona part és el fill dret de la raïl. El restant de l'arbre es construïx de forma similar. Este model representa a la busca binaria, començant des de la raïl, el subárbol esquerre o dret són recorreguts d'acort a si el valor buscat és menor o major que el valor present en el nodo actual, representant l'eliminació successiva dels elements.

En el pijor dels casos es realisen $\lfloor {\log }_{2}n+1\rfloor$iteraciones (del cicle de comparacions), a on la notació $\lfloor \rfloor$ denota la part sancera per baix de la funció. Esta cantitat de iteraciones és alcançada quan la busca alcança el nivell més profunt de l'arbre, equivalent a una busca binaria que es reduïx a un sol element, i en cada iteración, sempre elimina l'apany més chicotet dels dos si no tenen la mateixa cantitat d'elements.

Com a promig, assumint que cada element és igualment provable de ser buscat, despuix que la busca termine, el valor buscat serà més provable de ser trobat en el segon nivell de l'arbre. Açò és equivalent a una busca binaria que completa una iteración abans del pijor dels casos, alcançant-la despuix de ${\log }_{2}n-1$iteraciones. No obstant, l'arbre pot estar no balancejat, en el nivell més profunt parcialment complet, i equivalentemente, l'apany pot no estar dividit perfectament per la busca en algunes iteraciones, resultant que en la mitat de les voltes el menor subarreglo és eliminat. El promig actual del número de iteraciones és llaugerament major $({\log }_{2}n-\frac{n-{\log }_{2}n-1}{n})$. En el millor dels casos, a on l'element del mig de l'apany és igual al valor buscat, la seua posició és retornada despuix d'una iteración. En térmens de iteración, cap algoritme basat solament en comparacions pot exhibir millors promijos en el seu número de iteraciones que la busca binaria.

Cada iteración de la busca binaria definida anteriorment realisa una o dos comparacions, comprovant si l'element en el mig és igual al valor buscat en cada iteración. Assumint novament que cada element és igualment provable de ser buscat, cada iteración realisa com a promig 1.5 de comparacions. Una variació de l'algoritme comprova per l'igualtat en el final de cada busca, eliminant com a promig la mitat de les comparacions en cada iteración. En la majoria de les computadores el procediment anterior reduïx el temps de cada iteración molt poc, mentres que garantisa que la busca realise el major número de iteraciones possibles i com a promig adiciona una iteración més a la busca. Ya que el cicle de comparacions es realisa solament $\lfloor {\log }_{2}n+1\rfloor$voltes en el pijor dels casos, per a un n suficientment gran, el chicotet increment de l'eficiència producte de les comparacions en el cicle no compensa la iteración extra. Knuth 1998 va propondre un valor de $2^{66}$(més de 76 trillons) elements per a que esta variació anara més ràpida.

Cascada fraccional pot ser usada per a accelerar la busca del mateix valor en múltiples apanys. Es requerix $O(k\log n)$ per a buscar en cada apany l'element seleccionat, cascada fraccional ho reduïx a $O(k+\log n)$, a on k és el número d'apanys.

Vore també

• Método de bisecció