Căutarea binară

Căutarea binară e felul în care căutați un cuvânt în dicționar: îl deschideți la mijloc, vedeți dacă cuvântul e înainte sau după și repetați cu acea jumătate. Într-o listă sortată, găsește orice valoare dintr-un milion în cel mult 20 de comparații.

Un rând sortat de bare, cu bara din mijloc evidențiată, jumătate din rând estompată și o linie întreruptă la înălțimea valorii căutate
Un rând sortat de bare, cu bara din mijloc evidențiată, jumătate din rând estompată și o linie întreruptă la înălțimea valorii căutate

Ideea

Într-o listă sortată, o comparație vă spune mai mult decât dacă ați găsit valoarea căutată: vă spune de ce parte se află. Comparați valoarea căutată cu valoarea din mijloc. Dacă sunt egale, ați terminat. Dacă valoarea din mijloc e mai mică, tot ce e înaintea ei e și mai mic, deci valoarea căutată poate fi doar după ea. Dacă e mai mare, valoarea căutată poate fi doar înaintea ei. Păstrați doar acea jumătate și repetați.

Un exemplu

Căutați 23 în 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Valoarea din mijloc este 16, mai mică, deci rămân doar valorile de la 23 la 91. Mijlocul lor este 56, mai mare, deci rămân doar 23 și 38. Mijlocul lor este 23: găsită pe poziția 6 după 3 comparații, unde căutarea liniară are nevoie de 6. Căutarea lui 40 în aceeași listă compară 16, 56, 23 și 38, după care nu mai rămâne nimic: 4 comparații pentru a afla că 40 lipsește, față de 10 la căutarea liniară.

Înjumătățirile se adună repede

După o comparație rămâne cel mult jumătate din listă, după două un sfert, după k cel mult aproximativ n/2ᵏ. Căutarea se oprește când nu mai rămâne nimic, deci necesită cel mult ⌊log₂ n⌋ + 1 comparații: 6 pentru 40 de valori, 10 pentru 1.000, 20 pentru un milion și 30 pentru un miliard. O listă de două ori mai lungă adaugă doar o comparație. Se scrie O(log n).

Ușor de descris, greu de scris corect

John Mauchly a descris căutarea binară în 1946, dar, potrivit lui Donald Knuth, prima versiune care funcționa pentru orice lungime a listei nu a fost publicată decât în 1962. Jon Bentley a constatat mai târziu că doar cam unul din zece programatori profesioniști o scria corect: condițiile de oprire și plus sau minus unu la tăierea jumătăților sunt ușor de greșit. În 2006, Joshua Bloch a arătat că modul obișnuit de a afla mijlocul, (low + high) / 2, poate provoca depășire (overflow) la liste foarte lungi, o eroare care stătuse ani de zile în biblioteca Java. Scrierea low + (high − low) / 2, ca în aplicație, o evită.

John Mauchly (al cincilea din stânga) împreună cu alți responsabili ai ENIAC, în fața mașinii, într-o fotografie a armatei SUA. Mauchly a descris căutarea binară în 1946.
John Mauchly (al cincilea din stânga) împreună cu alți responsabili ai ENIAC, în fața mașinii, într-o fotografie a armatei SUA. Mauchly a descris căutarea binară în 1946.

Variante și utilizări

Când există duplicate, căutarea binară găsește una dintre potriviri; versiunile care continuă spre stânga sau spre dreapta găsesc prima sau ultima, ori poziția unde ar trebui inserată o valoare care lipsește. Aceeași idee a înjumătățirii găsește rădăcina unei ecuații (metoda bisecției), versiunea în care a apărut prima dată o eroare (git bisect) și răspunsul la multe probleme de optimizare. Arborii binari de căutare stochează datele astfel încât fiecare căutare să urmeze același drum al înjumătățirii.

Explorați

Deschideți aplicația, alegeți o valoare la Valoare de căutat și apăsați Pas. Zona umbrită e locul unde valoarea căutată mai poate fi; valoarea din mijloc e evidențiată, iar jumătatea eliminată se estompează. Casetele arată câte valori sunt încă posibile și câte comparații ar necesita căutarea liniară pentru aceeași valoare. Căutați o valoare care lipsește sau folosiți 40 de bare ca să vedeți cum crește diferența.

Întrebări frecvente

Care este complexitatea în timp a căutării binare?

O(log n): cel mult ⌊log₂ n⌋ + 1 comparații pentru n valori. În cel mai bun caz e o singură comparație, când valoarea căutată e la mijloc. Versiunea iterativă are nevoie de O(1) memorie suplimentară.

Care e diferența dintre căutarea binară și căutarea liniară?

Căutarea liniară verifică pe rând fiecare valoare și funcționează pe orice listă, dar poate avea nevoie de n comparații. Căutarea binară funcționează doar pe o listă sortată, dar elimină la fiecare comparație jumătate din ce a rămas, deci are nevoie de aproximativ log₂ n.

Merită să sortați o listă doar ca să folosiți căutarea binară?

Doar dacă o căutați de multe ori. Sortarea ia aproximativ n log n pași, mai mult decât o singură căutare liniară. Odată ce lista e sortată, fiecare căutare ulterioară e foarte ieftină.

Poate căutarea binară funcționa și pe altceva decât liste?

Da, pe orice unde un test vă spune de ce parte a răspunsului vă aflați: un interval de numere, versiunile unui program sau încercările dintr-un joc de tip „mai mare sau mai mic”.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Încercați căutarea binară