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 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.
Assignar 0 a L i a R (n − 1). Si L > R, la cerca acaba sense trobar el valor. Sigui m (la posició de l'element del mitjà) igual a la part sencera de (L + R) / 2. Si Am < T, igualar L a m + 1 i anar al pas 2. Si Am > T, igualar R a m – 1 i anar al pas 2. Si Am = 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.Bottenbruch, Hermann (1962).
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 miniatura|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.Flores, Ivan; Madpis, George (1971).
En el pitjor dels casos es realitzen 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 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 .Flores, Ivan; Madpis, George (1971).
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 vegades en el pitjor dels casos, per a un n prou 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 (més de 76 trilions) elements perquè aquesta variació anés més ràpida.Sloane, Neil.Rolfe, Timothy J. (1997).
La cascada fraccional pot ser utilitzada per accelerar la cerca del mateix valor en múltiples arranjaments. Cal per cercar a cada arranjament l'element seleccionat, trencada fraccional ho redueix a on k és el nombre d'arranjaments.Chazelle, Bernard; Liu, Ding (2001).
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.Beame, Paul; Fich, Faith E. (2001).
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.Bloom, Burton H. (1970).
Altres estructures de dades