Căutarea liniară
Căutarea liniară este ceea ce faceți când căutați un nume pe o listă nesortată: începeți de sus și citiți în jos până îl găsiți. Este cea mai simplă căutare care există, funcționează pe orice listă, iar pentru liste scurte este adesea tot ce vă trebuie.
Ideea
Comparați valoarea căutată cu prima valoare din listă. Dacă sunt egale, opriți-vă: valoarea căutată este pe poziția 1. Altfel, comparați-o cu a doua valoare, apoi cu a treia și așa mai departe. Dacă nici ultima valoare nu se potrivește, valoarea căutată nu este în listă. Nu trebuie să știți nimic dinainte despre listă: nu trebuie să fie sortată, iar valorile pot fi orice poate fi comparat pentru egalitate.
Un exemplu
Căutați 4 în 5, 1, 4, 2, 8. Este 5 egal cu 4? Nu. Dar 1? Nu. Dar 4? Da: găsit pe poziția 3 după 3 comparații. Acum căutați 7 în aceeași listă. Fiecare dintre cele cinci valori este verificată și niciuna nu se potrivește, așa că după 5 comparații răspunsul este că 7 nu există în listă.
Câte comparații
Găsirea unei valori de pe poziția k necesită k comparații. Dacă valoarea căutată poate fi la fel de probabil pe orice poziție, înseamnă în medie (n + 1)/2 comparații: 20,5 pentru 40 de valori. O valoare care lipsește necesită întotdeauna n, pentru că doar după ultima comparație este sigur că nicio valoare nu s-a potrivit. Așadar, costul crește proporțional cu lungimea listei, ceea ce se scrie O(n).
Căutările mai rapide au nevoie de ordine
Căutarea liniară nu poate sări peste nimic, pentru că într-o listă nesortată orice valoare poate fi oriunde. Odată ce lista este sortată, o comparație spune mai mult decât egal sau nu: spune de ce parte se află valoarea căutată. Căutarea binară folosește asta ca să înjumătățească lista la fiecare pas și are nevoie de circa log₂ n comparații, cel mult 6 pentru 40 de valori. Totuși, și sortarea costă timp, așa că pentru o listă în care se caută o singură dată căutarea liniară este adesea alegerea mai bună.
Mici îmbunătățiri
O variantă cu santinelă pune valoarea căutată la finalul listei înainte de căutare, astfel încât bucla trebuie să testeze doar potrivirea, nu și finalul listei. Mutarea unei valori cu o poziție în față, sau chiar pe primul loc, de fiecare dată când este găsită face ca valorile căutate des să coste mai puțin în timp. Niciuna nu schimbă cel mai rău caz de n comparații.
Explorați
Deschideți aplicația, alegeți o valoare la Valoare de căutat și apăsați Pas. Linia întreruptă arată înălțimea valorii căutate, fiecare valoare este evidențiată când este verificată și se estompează după ce este exclusă, iar o potrivire devine verde. Căutați o valoare care nu este în listă ca să vedeți o parcurgere completă sau dezactivați Oprire la prima potrivire și folosiți puține valori distincte ca să găsiți mai multe potriviri.
Întrebări frecvente
Care este complexitatea în timp a căutării liniare?
O(n) în cel mai rău caz și în medie, și O(1) în cel mai bun caz, când valoarea căutată este prima. Nu are nevoie de memorie suplimentară.
Care este diferența dintre căutarea liniară și căutarea binară?
Căutarea liniară verifică fiecare valoare în ordine și funcționează pe orice listă. Căutarea binară funcționează doar pe o listă sortată, dar la fiecare pas înjumătățește partea care poate conține valoarea căutată, așa că are nevoie de circa log₂ n comparații în loc de până la n.
Căutarea liniară are nevoie de o listă sortată?
Nu. Acesta este principalul ei avantaj. Pe o listă sortată se poate opri imediat ce trece de poziția unde ar fi valoarea căutată, dar tot este mai lentă decât căutarea binară.
Unde se folosește căutarea liniară?
Oriunde listele sunt scurte sau nesortate: găsirea unui element într-un tablou mic, parcurgerea unui fișier sau a unui flux care poate fi citit doar în ordine ori verificarea unei condiții pentru fiecare element. Multe funcții de bibliotecă, precum indexOf în JavaScript și list.index în Python, sunt căutări liniare.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați căutarea liniară