Căutarea prin salturi
Căutarea prin salturi e felul în care căutați o pagină într-o carte fără cuprins: răsfoiți înainte câte o bucată, aruncând o privire la numerele paginilor, iar când ați trecut prea departe, răsfoiți înapoi prin ultima bucată. Pe o listă sortată, necesită mult mai puține comparații decât verificarea fiecărei valori.
Ideea
Într-o listă sortată, ultima valoare a unui bloc arată dacă valoarea căutată poate fi măcar în acel bloc: dacă e mai mică decât valoarea căutată, toate valorile din bloc sunt și ele mai mici. Deci nu e nevoie să priviți înăuntru. Verificați pe rând ultima valoare a fiecărui bloc, sărind peste blocuri întregi, până când una nu e mai mică decât valoarea căutată. Atunci valoarea căutată poate fi doar în acel bloc: parcurgeți-l de la început.
Un exemplu
Căutați 23 în 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, cu blocuri de 3. Primul bloc se termină cu 8, care e mai mic, deci săriți peste el. Al doilea bloc se termină cu 23, care nu e mai mic, deci 23 poate fi doar printre 12, 16, 23. Parcurgerea dă 12, 16 și apoi 23: găsit după 5 comparații, față de 6 la căutarea liniară și 3 la căutarea binară. Căutând 40, capetele de bloc 8, 23 și 72 duc la blocul 38, 56, 72; 38 e mai mic, iar 56 deja mai mare, deci 40 nu e acolo: din nou 5 comparații.
De ce √n
Cu blocuri de m valori, găsirea blocului potrivit necesită cel mult aproximativ n/m comparații, iar parcurgerea lui cel mult m. Puține salturi lungi fac parcurgerea lungă; multe salturi scurte fac săriturile lungi. Suma n/m + m e cea mai mică atunci când ambele părți sunt egale, la m = √n, unde e aproximativ 2√n. Pentru 40 de valori, asta înseamnă blocuri de 6 și cel mult 13 comparații; pentru un milion de valori, blocuri de 1.000 și aproximativ 2.000 de comparații.
Unde se potrivește
Căutarea binară are nevoie de mai puține comparații, aproximativ log₂ n. Dar căutarea binară sare încoace și încolo prin toată lista, în timp ce căutarea prin salturi merge doar înainte și se întoarce o singură dată, la începutul unui bloc. Asta o făcea atractivă pentru date pe bandă magnetică sau într-o structură înlănțuită, unde întoarcerea e lentă. Ben Shneiderman a descris-o drept jump searching în 1978. Aceeași idee de împărțire în √n blocuri, numită adesea descompunere în radical, apare în mulți alți algoritmi.
Explorați
Deschideți aplicația, alegeți o valoare în Valoare de căutat și apăsați Pas. Fiecare salt evidențiază ultima valoare a unui bloc; blocurile sărite se estompează, iar blocul care poate conține valoarea căutată e umbrit cât timp e parcurs. Schimbați Lungimea saltului de la √n la 2 sau 8 cu 40 de bare și urmăriți cum se schimbă echilibrul dintre salturi și parcurgere.
Întrebări frecvente
Care este complexitatea în timp a căutării prin salturi?
O(√n) cu blocuri de √n valori: cel mult aproximativ 2√n comparații. Necesită O(1) memorie suplimentară și o listă sortată.
Care e diferența dintre căutarea prin salturi și căutarea binară?
Căutarea binară înjumătățește de fiecare dată partea rămasă și are nevoie de aproximativ log₂ n comparații, dar se mișcă înainte și înapoi. Căutarea prin salturi sare înainte în pași ficși și parcurge un singur bloc, are nevoie de aproximativ 2√n comparații și se întoarce o singură dată.
Poate parcurgerea ultimului bloc să folosească în schimb căutarea binară?
Da. Căutarea binară în bloc reduce parcurgerea de la m comparații la aproximativ log₂ m. Salturile costă tot n/m, așa că atunci merită blocuri mai mari.
Are nevoie căutarea prin salturi de o listă sortată?
Da. Săritul peste un bloc e sigur doar pentru că o ultimă valoare mai mică înseamnă că toate valorile din bloc sunt mai mici. Aplicația sortează mai întâi o listă nesortată.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați căutarea prin salturi