Căutare binară

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 20 martie 2021; verificările necesită 29 de modificări .

Căutarea binară (binară) (cunoscută și ca metoda bisecției sau dihotomie ) este un algoritm clasic pentru găsirea unui element într-o matrice sortată (vector) care utilizează împărțirea matricei în jumătăți. Folosit în informatică , matematică computațională și programare matematică .

Un caz special de căutare binară este metoda bisecției , care este folosită pentru a găsi rădăcinile unei funcții continue date pe un interval dat.

Găsirea unui element într-o matrice sortată

Determinarea valorii unui element în mijlocul unei structuri de date. Valoarea rezultată este comparată cu cheia.
Dacă cheia este mai mică decât valoarea din mijloc, atunci căutarea se efectuează în prima jumătate a elementelor, în caz contrar - în a doua.
Căutarea se reduce la faptul că valoarea elementului mijlociu din jumătatea selectată este din nou determinată și comparată cu cheia.
Procesul continuă până când este găsit fie elementul cu valoarea cheie, fie intervalul de căutare este gol.

Deși codul este destul de simplu, există câteva capcane.

Codul (first + last) / 2este eronat dacă firstși lastse încadrează individual în tipul lor, dar first+last nu [1] . Dacă matrice de o dimensiune atât de mare sunt teoretic posibile, trebuie să recurgem la trucuri:
- Utilizați cod first + (last - first) / 2care cu siguranță nu va duce la depășiri atunci când aveți de-a face cu numere întregi nenegative și primul<ultim.
  - Dacă firstși last sunt pointeri sau iteratori , un astfel de cod este singurul corect, deoarece nu încalcă abstractizarea (operația „pointer + pointer” este deja incorectă). Desigur, pentru a păstra complexitatea algoritmului, avem nevoie de operații rapide „pointer+număr → pointer”, „pointer−pointer → număr”.
- Dacă firstși last sunt tipuri semnate, efectuați calculul în tipul nesemnat: ((unsigned)first + (unsigned)last) / 2. În Java, următorul cod va funcționa: (first + last) >>> 1(adăugarea binară cu semnă este aceeași cu nesemnată, Java garantează acest comportament chiar și la depășire, iar această formulă întreagă funcționează pe numerele semnate ca nesemnate).
- Scrieți un calcul în assembler folosind indicatorul de transport . Ceva de genul add eax, b; rcr eax, 1. Dar nu este recomandabil să folosiți tipuri lungifirst + (last - first) / 2 , este mai rapid.
Erorile de la unul sunt frecvente în căutările binare și fiecare astfel de eroare se transformă într-o matrice buclă , sărită sau în afara limitelor. Prin urmare, este important să testați astfel de cazuri: o matrice goală ( n=0), un element ( n=1), căutând o valoare lipsă (prea mare, prea mică și undeva la mijloc), căutând primul și ultimul element.
Uneori se cere ca, dacă xexistă mai multe instanțe în lanț, să se găsească nu oricare, ci neapărat primul (opțional: ultimul; sau deloc x, ci elementul care îl urmează). [2] De exemplu, o funcție C++ găsește primul dintre egal și găsește elementul după x. Dacă nu se găsesc, ambele returnează locul unde se introduce.std::lower_boundstd::upper_bound

Omul de știință Jon Bentley susține că 90% dintre studenți, atunci când dezvoltă o căutare binară, uită să țină cont de oricare dintre aceste cerințe. Și chiar și în codul scris de Jon însuși și mergând din carte în carte, s-a strecurat o eroare: codul nu este rezistent la debordări [1] .

Exemplu de implementare Java

int binarySearch ( int [] arr , int cheie ) { int low = 0 ; int mare = arr . lungime - 1 ; în timp ce ( scăzut <= ridicat ) { int mid = ( scăzut + ridicat ) >>> 1 ; int midVal = arr [ mid ] ; if ( midVal < cheie ) scăzut = mijloc + 1 ; else if ( midVal > cheie ) ridicat = mijloc - 1 ; altfel întoarcere la mijloc ; // cheie găsită } întoarcere - ( scăzut + 1 ); // cheia nu a fost găsită. }

Aplicații

Aplicațiile practice ale metodei de căutare binară sunt variate:

Răspândit în informatică în legătură cu căutarea în structurile de date. De exemplu, căutarea în matrice de date este efectuată de cheia atribuită fiecăruia dintre elementele matricei (în cel mai simplu caz, elementul în sine este cheia).
Este, de asemenea, utilizat ca metodă numerică pentru găsirea unei soluții aproximative a ecuațiilor (vezi metoda Bisecției ).
Metoda este utilizată pentru a găsi extremul funcției obiectiv și în acest caz este o metodă de optimizare unidimensională condiționată . Când o funcție are un argument real, este posibil să se găsească o soluție până în intervalul de timp . Când argumentul este discret și inițial se află pe un segment de lungime N , căutarea unei soluții va dura timp. În final, pentru a căuta un extremum, să zicem, pentru certitudinea minimului , la pasul următor se aruncă unul dintre capetele segmentului considerat, valoarea în care este maximă. $\varepsilon$ $\log _{2}1/\varepsilon$ $1+\log _{2}N$

Vezi și

Note

↑ 1 2 Extra, Extra - Citește totul despre asta: aproape toate căutările binare și sortările de îmbinare sunt sparte Arhivat 2 decembrie 2013 la Wayback Machine // Joshua Bloch, Google Research; traducere — Aproape toate implementările de căutare binară și sortare de îmbinare au o eroare Arhivată 24 noiembrie 2013 la Wayback Machine
↑ În C++ std::lower_bound , găsește prima apariție a lui xși găsește std::upper_bound elementul care urmează x.

Literatură

Levitin A. V. Capitolul 4. Metoda de descompunere: Căutare binară // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 180-183. — 576 p. — ISBN 978-5-8459-0987-9
Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Metode de calcul pentru ingineri. — M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Metode numerice. - Ed. a 8-a. - M . : Laboratorul de Cunoștințe de bază, 2000.
Wirth N. Algoritmi + Structuri de date = Programe . - M . : " Mir " , 1985. - S. 28 .
Volkov E. A. Metode numerice. — M. : Fizmatlit, 2003.
Gill F., Murray W., Wright M. Optimizare practică. Pe. din engleza. — M .: Mir, 1985.
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algorithms: construction and analysis = Introduction to Algorithms / Ed. I. V. Krasikova. - Ed. a II-a. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .
Korn G., Korn T. Manual de matematică pentru oameni de știință și ingineri. - M . : Nauka, 1970. - S. 575-576.
Korshunov Yu. M., Korshunov Yu. M. Fundamentele matematice ale ciberneticii. - Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmi pentru rezolvarea problemelor de programare neliniară. — M .: MEPhI, 1982.
Robert Sedgwick. Algoritmi fundamentali în C. Fundamente/Structuri de date/Sortare/Căutare. - Sankt Petersburg. : DiaSoftYUP, 2003. - S. 672. - ISBN 5-93772-081-4 .