- Valoarea căutată
- Încă posibile
- Comparate
- Excluse
- Găsite
Căutarea exponențială
Căutarea exponențială găsește o valoare într-o listă sortată în două etape. Întâi se uită la pozițiile 1, 2, 4, 8, 16 și așa mai departe, dublând de fiecare dată, până când valoarea de acolo nu e mai mică decât valoarea căutată. Apoi caută binar în porțiunea dintre ultimele două poziții. Alegeți valoarea de căutat și vedeți de ce valorile de la început sunt găsite din doar câteva comparații. Apăsați Redare pentru a urmări căutarea sau Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași ca să săriți oriunde. Linia întreruptă marchează valoarea căutată, iar partea umbrită arată unde mai poate fi. Căutarea exponențială are nevoie de o listă sortată, așa că o listă nesortată este sortată mai întâi. Alegeți valoarea, câte bare sunt sau introduceți propriile numere. Cu tabla selectată, săgețile avansează câte un pas, bara de spațiu pornește și pune pauză, iar Home și End sar la început și la sfârșit.
Cum funcționează
- Alegeți valoarea de căutat și câte bare sunt. Sau introduceți propriile numere: căutarea exponențială le sortează mai întâi.
- Apăsați Redare sau folosiți Pas și Înapoi ca să avansați câte un pas. Trageți glisorul pentru pași ca să săriți oriunde în căutare.
- Căutați o valoare de la început și una de la sfârșit și comparați numărul cu Necesar la căutarea binară.
Cum funcționează căutarea exponențială
Uitați-vă la valoarea de pe poziția 1. Dacă e mai mică decât valoarea căutată, treceți la poziția 2, apoi 4, 8, 16, dublând de fiecare dată. Imediat ce o valoare nu e mai mică, vă opriți: valoarea căutată poate fi doar după poziția verificată anterior și înaintea acesteia. Căutați binar în acea porțiune. Dacă dublarea trece de sfârșitul listei, căutați binar de la ultima poziție verificată până la sfârșit.
Rapidă la început, fără să știe lungimea
Ca să ajungă la o valoare de pe poziția i, dublarea face cam log₂ i verificări, iar porțiunea găsită are mai puțin de i valori, deci căutarea binară mai face cam log₂ i. În total, cam 2 log₂ i, ceea ce depinde de unde e valoarea căutată, nu de cât de lungă e lista. Valorile de la început sunt găsite mai repede decât cu căutarea binară simplă; cele de la sfârșit costă până la aproximativ de două ori mai mult. Pentru că nu are niciodată nevoie de lungimea listei, merge și pe liste prea lungi ca să fie măsurate sau fără un sfârșit cunoscut.
Întrebări frecvente
Cum funcționează căutarea exponențială?
Pe o listă sortată verifică pozițiile 1, 2, 4, 8 și așa mai departe până când valoarea de acolo nu e mai mică decât valoarea căutată. Atunci valoarea căutată poate fi doar între ultimele două poziții verificate, iar o căutare binară în acea porțiune o găsește.
Este căutarea exponențială mai rapidă decât căutarea binară?
Când valoarea căutată e aproape de începutul listei, da: pentru o valoare de pe poziția i e nevoie de cam 2 log₂ i comparații, oricât de lungă ar fi lista. Când e aproape de sfârșit, căutarea binară simplă e mai rapidă, până la aproximativ de două ori.
La ce se folosește?
La căutarea în liste de lungime necunoscută sau nemărginită, cum ar fi un flux de date sau un șir infinit, și la interclasarea secvențelor sortate, unde următoarea potrivire e de obicei aproape. Modul galloping din Timsort folosește aceeași idee a dublării.
De ce se numește exponențială?
Pentru că pozițiile verificate cresc exponențial: 1, 2, 4, 8, 16, fiecare de două ori mai mare decât precedenta. Se mai numește căutare prin dublare sau galloping search.
Numerele mele sunt trimise undeva?
Nu. Căutarea rulează în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor