- Valoarea căutată
- Blocul curent
- Comparate
- Excluse
- Găsite
Căutarea prin salturi
Căutarea prin salturi se situează între căutarea liniară și cea binară. Străbate o listă sortată în salturi de m poziții, verificând doar ultima valoare din fiecare bloc, până ajunge la un bloc a cărui ultimă valoare nu e mai mică decât valoarea căutată. Apoi parcurge acel bloc de la început. Alegeți valoarea și lungimea saltului și urmăriți câte comparații necesită salturile și parcurgerea. Apăsați Redare pentru a urmări căutarea sau Pas și Înapoi pentru a avansa câte o comparație. Trageți glisorul pentru pași ca să săriți oriunde. Linia întreruptă marchează valoarea căutată, iar partea umbrită este blocul curent. Căutarea prin salturi are nevoie de o listă sortată, așa că o listă nesortată este sortată mai întâi. Alegeți valoarea, lungimea saltului, 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, lungimea saltului și câte bare sunt. Sau introduceți propriile numere: căutarea prin salturi le sortează mai întâi.
- Apăsați Redare sau folosiți Pas și Înapoi pentru a avansa câte o comparație. Trageți glisorul pentru pași ca să săriți oriunde în căutare.
- Încercați o lungime a saltului de 2 și de 8 cu 40 de bare și comparați numărul de comparații cu √n.
Cum funcționează căutarea prin salturi
Împărțiți lista sortată în blocuri de câte m valori. Priviți ultima valoare din primul bloc. Dacă e mai mică decât valoarea căutată, aceasta nu poate fi nicăieri în acel bloc, așa că săriți la sfârșitul blocului următor și priviți din nou. Imediat ce ultima valoare a unui bloc nu e mai mică, valoarea căutată poate fi doar în acel bloc: întoarceți-vă la începutul lui și verificați valorile una câte una până găsiți valoarea căutată sau treceți de ea.
Alegerea lungimii saltului
Cu n valori, salturile necesită până la n/m comparații, iar parcurgerea până la m. Salturile mici scurtează parcurgerea, dar salturile sunt multe; salturile mari fac invers. Totalul n/m + m e cel mai mic când m = √n, ceea ce dă aproximativ 2√n comparații: cel mult 13 pentru 40 de valori, față de 40 la căutarea liniară și 6 la căutarea binară. Căutarea prin salturi nu se întoarce niciodată mai mult de un bloc, ceea ce ajută când deplasarea înapoi prin date e lentă.
Întrebări frecvente
Cum funcționează căutarea prin salturi?
Pe o listă sortată, sare înainte în pași de m poziții și verifică ultima valoare din fiecare bloc. Când acea valoare nu mai e mai mică decât valoarea căutată, aceasta poate fi doar în acel bloc, pe care îl parcurge apoi de la început.
Care este cea mai bună lungime a saltului?
√n, rotunjit. Salturile costă până la n/m comparații, iar parcurgerea până la m, și suma lor e cea mai mică atunci când cele două sunt egale, la m = √n. Asta dă aproximativ 2√n comparații în cel mai rău caz.
Este căutarea prin salturi mai rapidă decât căutarea binară?
Nu, căutarea binară are nevoie de mai puține comparații: aproximativ log₂ n față de aproximativ 2√n. Căutarea prin salturi poate totuși câștiga când întoarcerea prin date e costisitoare, pentru că se întoarce o singură dată, la începutul unui bloc.
Ce potrivire găsește când valorile se repetă?
Prima. Fiecare bloc peste care sare se termină cu o valoare mai mică decât valoarea căutată, deci niciun bloc anterior nu poate conține o potrivire, iar parcurgerea începe de la începutul blocului.
Sunt trimise undeva numerele mele?
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