Căutarea exponențială

Căutarea binară trebuie să știe unde se termină lista înainte să se uite la mijloc. Căutarea exponențială nu: avansează în galop, cu pași tot mai mari, până trece de valoarea căutată, apoi caută binar în ultimul pas. Asta o face ideală pentru liste de lungime necunoscută și rapidă pentru valorile de la început.

Un rând sortat de bare cu salturi de lungime dublată peste pozițiile 1, 2, 4 și 8 și porțiunea dintre ultimele două salturi umbrită
Un rând sortat de bare cu salturi de lungime dublată peste pozițiile 1, 2, 4 și 8 și porțiunea dintre ultimele două salturi umbrită

Ideea

Verificați valoarea de pe poziția 1, apoi 2, 4, 8, 16 și așa mai departe, fiecare poziție de două ori mai departe decât precedenta. Cât timp valoarea de acolo e mai mică decât valoarea căutată, aceasta trebuie să fie mai încolo. Prima dată când o valoare nu e mai mică, valoarea căutată e prinsă: se află după poziția verificată anterior și nu mai departe de aceasta. Acea porțiune e sortată, deci o căutare binară găsește valoarea căutată sau arată că lipsește.

Un exemplu

Căutăm 23 în 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Pe poziția 1 e 2, pe poziția 2 e 5, pe poziția 4 e 12, toate mai mici. Pe poziția 8 e 56, care e mai mare, deci 23 poate fi doar pe pozițiile de la 5 la 7. Căutarea binară verifică mijlocul lor, poziția 6, și găsește 23: 5 comparații, față de 3 la căutarea binară simplă. Căutarea lui 12 în aceeași listă se oprește pe poziția 4 după 3 comparații, cu una mai puțin decât căutarea binară, iar 2 e găsit pe poziția 1 dintr-o singură comparație.

Câte comparații

Pentru o valoare de pe poziția i, dublarea se oprește după cam log₂ i pași și lasă o porțiune de mai puțin de i poziții, pe care căutarea binară o acoperă din încă cam log₂ i. Deci căutarea costă cam 2 log₂ i comparații, oricât de lungă ar fi lista. Când valoarea căutată e aproape de început, asta bate căutarea binară, care plătește mereu cam log₂ n. Când e aproape de sfârșit, căutarea exponențială plătește până la aproximativ de două ori mai mult. Pentru 40 de valori, aplicația face în medie cam 3 comparații pentru primele cinci poziții și cam 9 pentru ultimele cinci, față de cam 4,6 la căutarea binară.

Lungime necunoscută și galloping

Jon Bentley și Andrew Yao au descris această strategie de dublare în 1976 pentru căutarea nemărginită: găsirea unei valori într-un șir sortat fără sfârșit cunoscut, cum ar fi o listă infinită sau un flux de date pe care îl puteți doar interoga poziție cu poziție. Aceeași idee accelerează interclasarea. Când una din două secvențe sortate tot câștigă, Timsort trece în modul galloping: se uită cu 1, 2, 4, 8 poziții înainte în cealaltă secvență ca să găsească unde merge următoarea valoare, în loc să avanseze câte o poziție.

Explorați

Deschideți aplicația, alegeți o valoare în Valoare de căutat și apăsați Pas. Fiecare verificare a pozițiilor 1, 2, 4, 8 și așa mai departe e evidențiată; imediat ce o valoare nu e mai mică, porțiunea dintre ultimele două poziții e umbrită și preia căutarea binară. Căutați o valoare mică și apoi una mare și comparați numărul cu caseta pentru căutarea binară.

Întrebări frecvente

Care este complexitatea în timp a căutării exponențiale?

O(log i) pentru o valoare de pe poziția i, deci cel mult O(log n) pentru o listă de n valori. Are nevoie de O(1) memorie suplimentară și de o listă sortată.

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

Căutarea binară pornește de la toată lista și are nevoie de lungimea ei. Căutarea exponențială găsește întâi, prin dublare, o porțiune care conține valoarea căutată, apoi caută binar doar în acea porțiune. E mai rapidă când valoarea căutată e aproape de început și funcționează fără să știe lungimea.

De ce se dublează pasul în loc să se adune o valoare fixă?

Adunarea unui pas fix înseamnă căutarea prin salturi (jump search), care are nevoie de cam n împărțit la pas verificări ca să parcurgă lista. Dublarea ajunge la poziția i din cam log₂ i verificări, iar porțiunea rămasă nu e niciodată de mai mult de două ori prea mare, deci căutarea binară de după rămâne scurtă.

Unde se folosește căutarea exponențială?

La căutarea în date sortate nemărginite sau foarte lungi, la interclasarea secvențelor sortate (galloping în Timsort) și la găsirea primei poziții în care o condiție devine adevărată când nu se cunoaște o limită superioară.

Ești gata să încerci?

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

Încercați căutarea exponențială