Cerca binària

En ciències de la computació i matemàtiques, la cerca binària, també coneguda com a cerca d'interval mitjà o cerca logarítmica, és un algorisme de cerca que troba la posició d'un valor en un array ordenat. Compara el valor amb l'element en el mitjà del array, si no són iguals, la meitat en la qual el valor no pot estar és eliminada i la cerca continua en la meitat restant fins que el valor es trobi.La cerca binària és computada en el pitjor dels casos en un temps logarítmic, realitzant $O{\bigl (}\log n{\bigr )}$comparacions, on n és el nombre d'elements de l'arranjament i log és el logaritme. La cerca binària requereix solament O(1) en espai, és a dir, que l'espai requerit per l'algorisme és el mateix per a qualsevol quantitat d'elements en el array. Encara que estructures de dades especialitzades en la cerca ràpides com les taules hash poden ser més eficients, la cerca binària s'aplica a un ampli rang de problemes de cerca.

Encara que la idea és simple, implementar la cerca binària correctament requereix atenció a alguns detalls com la seva condició de parada i el càlcul del punt mitjà d'un interval. Existeixen nombroses variacions de la cerca binària. Una variació particular (cascada fraccional) accelera la cerca binària per a un mateix valor en múltiples arranjaments.

Algorisme

La cerca binària funciona en arranjaments ordenats. La cerca binària comença per comparar l'element del mitjà de l'arranjament amb el valor buscat. Si el valor buscat és igual a l'element del mitjà, la seva posició en l'arranjament és retornada. Si el valor buscat és menor o major que l'element del mitjà, la cerca contínua en la primera o segona meitat, respectivament, deixant l'altra meitat fora de consideració.

Procediment

Donat un arranjament A de n elements amb valors A0 ... An−1, ordenats tal que A0 ≤ ... ≤ An−1, i un valor buscat T, el següent procediment usa cerca binària per trobar l'índex de T en A.

1. Assignar 0 a L i a R (n − 1).
2. Si L > R, la cerca acaba sense trobar el valor.
3. Sigui m (la posició de l'element del mitjà) igual a la part sencera 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 cerca va acabar, retornar m.

Aquest procediment iteratiu manté els límits de la cerca mitjançant dues variables. Algunes implementacions realitzen la comparació d'igualtat al final de l'algorisme, com resultant s'obté un cicle més ràpid de comparacions però s'augmenta en un la quantitat d'iteracions mitjanes.

Coincidències aproximades

El procediment anterior només realitza coincidències exactes, trobant la posició del valor buscat. No obstant això, donat l'ordre natural dels arranjaments ordenats, és trivial estendre la cerca binària per realitzar coincidències aproximades. Per exemple, la cerca binària pot ser usada per computar, per a un valor donat, el seu rank (el nombre d'elements menors), antecessor (proper element menor), successor(proper element major), i veïns propers. Les consultes en intervals, com per exemple, buscar el nombre d'elements entre dos nombres poden ser computades amb dues preguntes de rank.

• Les consultes de rank poden ser realitzades usant una modificació de la cerca binària, retornant m en les cerques on es trobi l'element, i L on no es trobi, corresponent aquest últim al nombre d'elements menors que el valor buscat.
• Les consultes d'antecessor i successor poden ser computades amb preguntes de rank també. Una vegada que el rank del valor buscat és conegut, el seu antecessor és l'element en la posició donat per la seva rank(l'element major que és menor que el valor buscat). El seu successor és l'element després del (si ell està present en l'arranjament) o en la posició següent a l'antecessor (en un altre cas). El veí més proper del valor buscat és el seu antecessor o el seu successor, dels dos el més proper.
• Les consultes de rang són també fàcils de manipular. Una vegada que els rank de tots dos valors són coneguts, el nombre d'elements majors o iguals al primer valor i menors que el segon és la diferència dels dos ranks. Aquesta quantitat pot disminuir o augmentar d'acord si els extrems de l'interval han de ser considerats part de la pregunta en qüestió i quan l'arranjament contingui claus que coincideixin amb els extrems.

Rendiment

Un arbre que representa l'algorisme de cerca binària. L'arranjament en el qual s'usa l'algorismes és [20, 30, 40, 50, 90, 100], i el valor buscat és 40.

El rendiment de la cerca binària pot ser analitzada reduint l'algorisme a un arbre binari de cerca, on l'arrel és l'element en el mitjà de l'arranjament, l'element en el mitjà de la primera part de l'arranjament és el fill esquerre de l'arrel i l'element en el mitjà de la segona part és el fill dret de l'arrel. La resta de l'arbre es construeix de forma similar. Aquest model representa a la cerca binària, començant des de l'arrel, el subarbre esquerre o dret són recorreguts d'acord amb si el valor buscat és menor o major que el valor present en el node actual, representant l'eliminació successiva dels elements.

En el pitjor dels casos es realitzen $\lfloor \log _{2}n+1\rfloor$iteracions (del cicle de comparacions), on la notació denota la part sencera per sota de la funció. Aquesta quantitat d'iteracions és aconseguida quan la cerca aconsegueix el nivell més profund de l'arbre, equivalent a una cerca binària que es redueix a un sol element, i en cada iteració, sempre elimina l'arranjament més petit dels dos si no tenen la mateixa quantitat d'elements. Com a mitjana, assumint que cada element és igualment probable de ser buscat, després que la cerca acabi, el valor buscat serà més probable de ser trobat en el segon nivell de l'arbre. Això és equival a una cerca binària que completa una iteració abans del pitjor dels casos, aconseguint-la després de $\log _{2}n-1$iteracions. No obstant això, l'arbre pot estar no balancejat, amb el nivell més profund parcialment complet, i equivalentment, l'arranjament vaig poder no estar dividit perfectament per la cerca en algunes iteracions, resultant que en la meitat de les vegades el menor sub-arreglo és eliminat. La mitjana actual del nombre d'iteracions és lleugerament major ${\bigl (}\log _{2}n-{\frac {n-\log _{2}n-1}{n}}{\bigr )}$.

En el millor dels casos, on l'element del mitjà de l'arranjament és igual al valor buscat, la seva posició és retornada després d'una iteració. En termes d'iteració, cap algorisme basat solament en comparacions pot exhibir millors mitjanes en el seu nombre d'iteracions que la cerca binària.Cada iteració de la cerca binària definida anteriorment realitza una o dues comparacions, comprovant si l'element en el mitjà és igual al valor buscat en cada iteració. Assumint novament que cada element és igualment probable de ser buscat, cada iteració realitza com a mitjana 1.5 de comparacions. Una variació de l'algorisme comprova per la igualtat en el final de cada cerca, eliminant com a mitjana la meitat de les comparacions en cada iteració. En la majoria de les computadores el procediment anterior redueix el temps de cada iteració molt poc, mentre que garanteix que la cerca realitzi el major nombre d'iteracions possibles i com a mitjana addiciona una iteració més a la cerca. Atès que el cicle de comparacions es realitza només $\lfloor \log _{2}n+1\rfloor$vegades en el pitjor dels casos, per a un n suficientment gran, el petit increment de l'eficiència producte de les comparacions en el cicle no compensa la iteració extra. Knuth 1998 va proposar un valor de $2^{66}$(més de 76 trilions) elements perquè aquesta variació anés més ràpida.

La cascada fraccional pot ser utilitzada per accelerar la cerca del mateix valor en múltiples arranjaments. Es requereix $O(k\log n)$per cercar a cada arranjament l'element seleccionat, trencada fraccional ho redueix a $O(k+\log n)$on k és el nombre d'arranjaments.

Comparació de la cerca binària amb altres esquemes

La tècnica d'usar arranjaments ordenats amb cerca binària és una solució molt ineficient quan la inserció i l'eliminació són necessàries.

Altres algorismes suporten més eficientment la inserció i l'eliminació, i també un muntatge més ràpid i exacte.

Hashing

Per implementar arranjaments associatius, taules hash, una estructura que mapeja claus contra valors usant una funció de hash, són generalment més ràpides que la cerca binària en arranjaments ordenats de valors; la majoria de les implementacions requereix com a mitjana un temps amortitzat constant. No obstant això, hashing no és molt útil per a comparacions aproximades, tals com a antecessor, successor, i veí més proper, atès que la informació que ens presenta en la cerca és si el valor està present o no. La cerca binària és ideal per a aquest tipus de comparacions, realitzant-les en temps logarítmic.

Arbres

Un arbre binari de cerca és una estructura de dades que funciona basat en el principi de la cerca binària: els valors de l'arbre estan col·locats en forma ordenada, i el recorregut de l'arbre és realitzat usant un algorisme molt semblant a la cerca binària. La inserció i eliminació requereixen igual que el recorregut un temps logarítmic. Aquest cost és molt millor que el cost lineal de la inserció i eliminació en els arranjaments ordenats, i els arbres de cerca binària posseeixen l'habilitat de realitzar totes les operacions possibles en els arranjaments ordenats, incloent consultes en rangs i comparacions aproximades.

No obstant això, la cerca binària és usualment més eficient per realitzar cerques posat que els arbres binaris de cerca estaran probablement desbalancejats, donant com a conseqüència un cost computacional superior a la cerca binària.

Els arbres binaris de cerca s'utilitzen per realitzar cerques ràpides en dispositius d'emmagatzematges externs, on les dades necessiten ser buscats i col·locats en la memòria principal. Dividint l'arbre en pàgines amb una quantitat determinada d'elements resultat que la cerca en l'arbre binari tingui un menor cost computacional que els cercadors convencionals dels discos. Noti que aquest procés crea un arbre multipropòsit, ja que cada pàgina està connectada una amb una altra. L'arbre-B generalitza aquest mètode de l'organització en l'arbre, els Arbol-B són freqüentment utilitzats per organitzar llargs conjunts de dades com les bases de dades o els sistemes de fitxers.

Cerca lineal

La cerca lineal és un simple algorisme de cerca que comprova cada element fins que trobi el valor buscat. La cerca lineal pot ser implementada en una llista enllaçada, que ens permet insercions i eliminacions més eficients que un arranjament. La cerca binària és més eficient que la cerca lineal en els arranjaments ordenats, exceptuant els arranjaments que contingui pocs elements. Si l'arranjament ha de ser ordenat primer, aquest cost ha de ser amortitzat sobre qualsevol cerca. Ordenar l'arranjament també ens permet comparacions aproximades més eficients, entre altres operacions.

Aproximacions mixtes

L'arranjament de Judy usa un conjunt d'idees per aconseguir una solució més eficient.

Algorismes de classificació

Un problema relacionat amb la cerca és la classificació. Qualsevol algorisme que realitzi cerques, com la cerca binària, pot ser usat per classificar també. Existeixen altres algorismes més específics per a la classificació, un arranjament de bit és el més simple, usat quan el rang dels elements és limitat, és molt ràpid, ja que requereix un temps constant.

Per a resultats aproximats, els filtres de Bloom, una altra estructura de dada probabilista basada en hashing, guarda un conjunt de valors codificant els valors amb arranjaments de bits i múltiples funcions de hash. Els filtres de Bloomson molt més eficaços que els arranjaments de bits quant a espai en la majoria dels casos i molt més lents.

Altres estructures de dades

Existeixen estructures de dades que poden realitzar cerca binària en arranjaments ordenats. Per exemple, les cerques, les comparacions parcials i totes les operacions permeses en arranjaments ordenats poden ser realitzades de manera més eficient que amb la cerca binària amb estructures com els arbres de van Emde Boes, arbres de fusió, tries, i arranjaments de bits. No obstant això, mentre que aquestes operacions poden ser realitzades eficientment en els arranjaments ordenats sense importància de qual sigui el tipus dels elements, aquest tipus d'estructura de dades són usualment més eficients perquè exploten les propietats del conjunt d'elements de l'arranjament.

Variacions

Cerca binària uniforme

La cerca binària uniforme guarda l'índex de l'element del mitjà i el nombre d'elements al voltant de l'element del mitjà que no hem eliminat encara. Cada pas redueix la grandària de l'arranjament aproximadament en la meitat. Aquesta variació és uniforme perquè la diferència entre els índexs dels elements del mitjà i l'element escollit en la iteració anterior roman constant per a arranjaments de la mateixa grandària.

Cerca Fibonacci

Cerca Fibonacci en la funció $f{\bigl (}x{\bigr )}=\sin {\bigl (}{\bigl (}x+{\frac {1}{10}}{\bigr )}\pi {\bigr )}$ en l'interval $[0,1]$ En l'exemple anterior l'algorisme troba un interval que conté el màxim de $f$ amb una longitud menor o igual a ${\frac {1}{10}}$. En tres iteracions, retorna l'interval $[{\frac {5}{13}},{\frac {6}{13}}]$, amb una longitud d'${\frac {1}{13}}$

La cerca Fibonacci és un mètode similar a la cerca binària que successivament redueix la grandària de l'interval al com el màxim d'una funció unimodal pertany. Donat un interval finit, una funció unimodal, i la màxima longitud de l'interval resultant, la cerca Fibonacci troba un nombre de Fibonacci tal que si l'interval es divideix en aquesta quantitat de subintervals d'igual longitud, els subintervals seran menors que la màxima longitud. Després de dividit l'interval, elimina els subintervals als quals el màxim no pertany fins que romanguin un o més subintervals continus.

Cerca exponencial

La cerca exponencial és un algorisme per buscar principalment en llistes infinites, però pot ser aplicada per seleccionar el límit superior de la cerca binària. Comença trobant el primer element que compleix que és una potència de dues i major que el valor buscat, després, fixa aquest índex com el límit superior de la cerca binària, i canvia cap a la cerca binària. La cerca realitza $\lfloor \log _{2}x+1\rfloor$iteracions de la cerca exponencial i li sumo $\lfloor \log _{2}x\rfloor$iteracions de la cerca binària, on $x$és la posició del valor buscat. Solament si el valor buscat està prop del principi de l'arranjament és que aquesta variació és més eficient que seleccionar el major element com el límit superior.

Cerca d'interpolació

Al contrari de la cerca binària, la cerca d'interpolació no calcula el punt mitjà sinó que realitza diversos intents a la recerca del valor requerit, prenent en compte el menor i major element de l'arranjament així com la seva longitud. Aquest procediment és solament possible si els elements de l'arranjament són nombres. Es basa en la hipòtesi que l'element del mitjà no és la millor opció en molts casos; per exemple, si l'element buscat aquesta proper al major element de l'arranjament, és molt probable que aquest situat en el final de l'arranjament. Qua la distribució dels elements en l'arranjament és uniforme properament, es realitzen $O{\bigl (}\log \log n{\bigr )}$comparacions.A la pràctica, la cerca d'interpolació és més ineficient que la cerca binària per a arranjaments petits, atès que la cerca per interpolació requereix un conjunt de còmputs extres, i la taxa de creixement de la seva complexitat sol es compensa per a arranjaments grans.

Cascada fraccional

Cascada fraccionària és una tècnica que accelera la cerca binària del mateix element en arranjaments ordenats. La cerca e cada arranjament pren $O{\bigl (}k\log n{\bigr )}$on $k$és el nombre d'arranjaments. Cascada fraccionària redueix aquest cost a $O{\bigl (}k+\log n{\bigr )}$emmagatzemant informació específica en cada arranjament sobre els altres arranjaments.

Cascada fraccionària va ser desenvolupada originalment per resoldre eficientment diversos problemes de geometria computacional, però també ha estat aplicada en dominis amb l'encaminamient dels protocols d'internet.

Història

En 1946, John Mauchly va esmentar per primera vegada la cerca binària com a part de Moore School Lectures, el primer conjunt de conferències relacionat amb les computadores. Les següents publicacions esmentaven que la cerca binària només funcionava en arranjaments la longitud dels quals anés d'un menys que una potència de dues fins a 1960, quan Derrick Henry Lehmer publicà un algorisme de cerca binària que funcionava en tots els arranjaments ordenats. En 1962, Hermann Bottenbruch va presentar en ALGOL 60 una implementació de l'algorisme de cerca binària en el qual col·locava la comparació d'igualtat en el final de l'algorisme, incrementant el nombre faig una mitjana de d'iteracions per un, però reduint a un el nombre de comparacions per iteració. La cerca binària uniforme va ser presentada a Donald Knuth en 1971 per a. K. Chandra de la Universitat Stanford i publicat en el llibre de Knuth: The Art of Computer Programming. En 1986, Bernard Chazelle i Leonidas J. Guibas van introduir trencada fraccional, una tècnica usada per accelerar la cerca binària en múltiples arranjaments.

Problemes d'implementació

Quan Jon Bentley va assignar la cerca binària com un problema en un curs de programadors professionals, es va adonar que el noranta per cent fallava a desenvolupar una solució correcta. Després de diverses hores de treball i un altre estudi publicat en 1988 mostra que el codi correcte sol es troba en cinc de cada vint mostres preses. A més la pròpia implementació de cerca binària de Bentley, publicada en el seu llibre de 1986 Programming Pearls, contenia un error de desbordament (overflow) que va romandre sense ser detectat per més de vint anys, a més la implementació de la biblioteca del llenguatge de programació Java de la cerca binària va tenir el mateix error durant més de nou anys.

En una implementació pràctica, les variables utilitzades per representar els índexs sovint seran de grandària fixa, i això pot donar lloc a un desbordament aritmètic per a arranjaments molt grans. Si el punt mitjà de l'interval es calcula com (L + R) / 2, llavors el valor de L + R pot excedir el rang d'enters del tipus de dades usat per emmagatzemar el punt mitjà, fins i tot si L i R estan dins del rang. Si L i R no són negatius, això es pot evitar calculant el punt mitjà com a L + (R - L) / 2.

Si el valor buscat és major que el valor màxim de l'arranjament i l'últim índex de l'arranjament és el valor màxim representable de L, el valor de L eventualment es convertirà en massa gran i ocorrerà un desbordament. Un problema similar ocorrerà si el valor buscat és menor que el menor valor en l'arranjament i el primer índex de l'arranjament és el valor representable més petit de R. En particular, això significa que R no ha de ser un tipus sense signe si l'arranjament comença amb índex 0..

Un bucle infinit pot ocórrer si les condicions de sortida per al bucle no estan definides correctament. Una vegada L supera R, la cerca ha fallat i ha de transmetre el fracàs de la cerca. A més, el bucle ha de sortir quan es troba l'element de destinació, o en el cas d'una implementació on aquest control es mou al final, comprova si la cerca va tenir èxit o va fallar al final ha d'estar en el seu lloc. Bentley va trobar que, en la seva assignació de cerca binària, aquest error va ser realitzat per la majoria dels programadors que no van implementar correctament una cerca binària.

Suport de biblioteca

Les biblioteques estàndard de molts llenguatges de programació inclouen implementacions de la cerca binària:

• C proporciona la funció bsearch() a la seva biblioteca estàndard, la qual és típicament implementada mitjançant cerca binària (a pesar que l'estàndard no ho requereix així).
• C++ STL proporciona les funcions binary_search()(), lower_bound(), upper_bound() i equal_range().
• COBOL proporciona el verb SEARCH ALL per realitzar cerques binàries en taules COBOL ordenades.
• Java ofereix un conjunt de mètodes estàtics de binarySearh() a la classe Arrays i Col·leccions en el paquet estàndard java.util per realitzar cerques binàries en els Arranjaments i en les Llistes de Java.
• Microsoft's .NET Franmework 2.0 ofereix versions genèriques estàtiques de la cerca binària en la seva col·lecció de classes. Un exemple seria Sistema. Array's BinarySearch<T>(T[] array, T valor).
• Python proporciona el modulo bisect.
• La classe de Array de Ruby inclou un mètode bsearch amb coincidència aproximada incorporada.
• El paquet de biblioteca estàndard: sort de Go conté les funcions Search, SearchInts, SearchFloat64s i SearchStrings, que implementen la cerca binària general, així com implementacions específiques per buscar segments de nombres enters, nombres de punt flotant i cadenes, respectivament.
• Per Objective-C, el marc de Cacau proporciona el NSArray -indexOfObject:inSortedRange:opcions:usingComparator: mètode en Mac US X 10.6+. Apple's Core Foundation C framework també conté un CFArrayBSearchValues() funció.

Enllaços externs

• NIST Dictionary of Algorithms and Data Structures: binary search.