- Valoarea căutată
- Comparate
- Excluse
- Găsite
Căutarea liniară
Căutarea liniară este cel mai simplu mod de a găsi o valoare: porniți de la început și verificați fiecare valoare pe rând până apare. Funcționează pe orice listă, sortată sau nu. Alegeți valoarea căutată, redați căutarea sau parcurgeți-o câte o comparație și urmăriți cum costul depinde de locul valorii sau de faptul că ea există sau nu. 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ă. Alegeți valoarea, câte bare sunt, cum încep sau introduceți propriile numere. Dezactivați Oprire la prima potrivire ca să găsiți toate potrivirile. 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 căutată, câte bare sunt și cum încep. Sau introduceți propriile numere.
- Apăsați Redare sau folosiți Pas și Înapoi ca să avansați câte o comparație. Trageți glisorul pentru pași ca să săriți oriunde în căutare.
- Dezactivați Oprire la prima potrivire ca să verificați fiecare valoare și să găsiți toate potrivirile.
Cum funcționează căutarea liniară
Comparați prima valoare cu valoarea căutată. Dacă sunt egale, ați terminat. Dacă nu, treceți la a doua valoare, apoi la a treia și așa mai departe. Dacă ajungeți la finalul listei fără nicio potrivire, valoarea căutată nu este în listă. Nu trebuie pregătit nimic: lista nu trebuie să fie sortată.
Câte comparații
O valoare de pe poziția k este găsită după k comparații. Cel mai bun caz este o singură comparație, când valoarea căutată este prima. Cel mai rău caz este n, când este ultima sau lipsește, pentru că doar după ce verificați fiecare valoare puteți fi siguri că nu există. În medie, pentru o valoare care este în listă, sunt necesare circa (n + 1)/2. Pentru o listă sortată, căutarea binară se descurcă mult mai bine: circa log₂ n comparații, 6 în loc de până la 40 pentru 40 de valori.
Întrebări frecvente
Cum funcționează căutarea liniară?
Verifică valorile unei liste una câte una, de la prima la ultima, până găsește valoarea căutată sau rămâne fără valori. Se mai numește căutare secvențială.
Care este complexitatea în timp a căutării liniare?
O(n): în cel mai rău caz, când valoarea căutată este ultima sau lipsește, o compară cu toate cele n valori. În medie, pentru o valoare care este în listă, sunt necesare circa (n + 1)/2 comparații.
Când este căutarea liniară o alegere bună?
Pentru liste scurte, pentru liste nesortate în care se caută doar o dată sau de două ori și pentru date care pot fi citite doar în ordine, cum ar fi un flux. Sortarea prealabilă, ca să puteți folosi căutarea binară, merită doar dacă veți căuta de multe ori.
De ce costă cel mai mult o valoare care lipsește?
Pentru că nimic nu îi spune căutării liniare să se oprească mai devreme. O potrivire poate fi exclusă doar verificând fiecare valoare, așa că o valoare care nu este în listă necesită întotdeauna n comparații.
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