- Doel
- Vergeleken
- Uitgesloten
- Gevonden
Lineair zoeken
Lineair zoeken is de eenvoudigste manier om een waarde te vinden: begin vooraan en controleer elke waarde om de beurt tot je haar tegenkomt. Het werkt op elke lijst, gesorteerd of niet. Kies de waarde die je zoekt, speel het zoeken af of doorloop het per vergelijking, en zie hoe de kosten afhangen van waar de waarde staat, en of ze er wel staat. Druk op Afspelen om het zoeken te volgen, of gebruik Stap en Terug om per vergelijking te gaan. Sleep de stappenschuif om ergens naartoe te springen. De stippellijn geeft de waarde aan die je zoekt. Kies de waarde, hoeveel staven, hoe ze beginnen, of typ je eigen getallen. Zet Stop bij de eerste treffer uit om elke treffer te vinden. Als het bord geselecteerd is, zetten de pijltjestoetsen een stap, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het eind.
Hoe het werkt
- Kies de waarde om naar te zoeken, hoeveel staven en hoe ze beginnen. Of typ je eigen getallen.
- Druk op Afspelen, of gebruik Stap en Terug om per vergelijking te gaan. Sleep de stappenschuif om naar elk punt in het zoeken te springen.
- Zet Stop bij de eerste treffer uit om elke waarde te controleren en alle treffers te vinden.
Hoe lineair zoeken werkt
Vergelijk de eerste waarde met de doelwaarde. Zijn ze gelijk, dan ben je klaar. Zo niet, ga dan door naar de tweede waarde, dan de derde, enzovoort. Bereik je het eind van de lijst zonder treffer, dan staat de doelwaarde niet in de lijst. Je hoeft niets voor te bereiden: de lijst hoeft niet gesorteerd te zijn.
Hoeveel vergelijkingen
Een waarde op plek k vind je na k vergelijkingen. In het beste geval is dat één vergelijking, als de doelwaarde vooraan staat. In het slechtste geval zijn het er n, als ze achteraan staat of ontbreekt, want pas als je elke waarde hebt gecontroleerd, weet je zeker dat ze er niet is. Gemiddeld kost een waarde die in de lijst staat ongeveer (n + 1)/2. Voor een gesorteerde lijst doet binair zoeken het veel beter: ongeveer log₂ n vergelijkingen, 6 in plaats van tot 40 bij 40 waarden.
Veelgestelde vragen
Hoe werkt lineair zoeken?
Het controleert de waarden van een lijst een voor een, van de eerste tot de laatste, tot het de doelwaarde vindt of de waarden op zijn. Het heet ook sequentieel zoeken.
Wat is de tijdcomplexiteit van lineair zoeken?
O(n): in het slechtste geval, als de doelwaarde achteraan staat of ontbreekt, vergelijkt het de doelwaarde met alle n waarden. Gemiddeld kost een doelwaarde die in de lijst staat ongeveer (n + 1)/2 vergelijkingen.
Wanneer is lineair zoeken een goede keuze?
Voor korte lijsten, voor ongesorteerde lijsten die maar een of twee keer worden doorzocht, en voor gegevens die je alleen op volgorde kunt lezen, zoals een stream. Eerst sorteren zodat je binair zoeken kunt gebruiken, loont alleen als je vaak zoekt.
Waarom kost een ontbrekende waarde het meest?
Omdat niets lineair zoeken vertelt dat het eerder kan stoppen. Een treffer kun je alleen uitsluiten door elke waarde te controleren, dus een waarde die niet in de lijst staat kost altijd n vergelijkingen.
Worden mijn getallen ergens naartoe gestuurd?
Nee. Het zoeken draait in je browser, en je laatste instellingen blijven in de lokale opslag van deze browser.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor