Busca binària

Busca binària

En ciències de la computació i matemàtiques, la busca binària, 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 de l'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 binària é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 logaritme. La busca binària 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 binària s'aplica a un ampli ranc de problemes de busca.

Encara que l'idea és simple, implementar la busca binària 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 binària. Una variació particular (cascada fraccional) accelera la busca binària per a un mateix valor en múltiples apanys.

Algoritme

La busca binària funciona en apanys ordenats. La busca binària 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 binària 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 binària per a realisar coincidències aproximades. Per eixemple, la busca binària 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 binària, 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 binària. 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 binària pot ser analisada reduint l'algoritme a un arbre binari 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 binària, 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 binària 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 binària 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 binària.

Cada iteración de la busca binària 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ó