Analyseren en zoekopdrachten verbeteren

Op deze pagina, ga je zien hoe de eigenschappen van een lijst beïnvloeden hoe een algoritme de lijst doorzoekt.

Zoeken in Ongesorteerde Data

Wanneer je naar een specifiek element zoekt in ongesorteerde data, moet je alle elementen checken totdat je de gezochte waarde vindt.

Geen Afbeelding
  1. Bouw een positie van getal in ongesorteerde lijstblok dat aangeeft wat de eerste locatie van een specifiek getal in een ongesorteerde lijst is. Als het getal niet gevonden kan worden, dan rapporteert het blok "Niet in lijst" (of "NIL", als je dat liever hebt).
    Geen Afbeelding
Het zoeken in ongesorteerde data kan lang duren als er heel veel data is, maar voor een lijst met weinig data gaat het heel snel.

Zoeken in Gesorteerde Data

Als je naar een nummer aan het zoeken bent in gesorteerde data heb je al meer informatie. Stel je voor dat je een gesorteerde lijst hebt en je wil achter de locatie van een getal komen.

Normaal gesproken zijn gesorteerde lijsten van laag naar hoog gesorteerd. Je gaat nog een blok maken dat een lijst van getallen sorteert in Hoofdstuk 8, Een Lijst Sorteren.
Alex: Als de lijst gesorteerd is kunnen we kijken naar het middelste element van de lijst en kijken of dat dat nummer in de eerste of laatste helft van de lijst staat. Dat zou ons tijd besparen.
Bo: Dit is een beetje zoals het raad-het-getalspel dat we hebben gemaakt: ik kies een getal en de computer probeert het te raden door de lijst in tweeën te splitsen bij elke gok.
Geen Afbeelding
Alex: Maar bij dat spel raadde de computer een getal dat wij hadden gekozen. Nu willen we een getal vinden in een lijst en daarvan de positie rapporteren. Het zou zo moeten werken:
Geen Afbeelding
Bo: Ja maar het voelt nog steeds hetzelfde. Het zou dezelfde opbouw moeten hebben.
Bo's laatste opmerking is een manier van abstractie. Bo merkte op dat positie in gesorteerde lijst en het Raad-het-getal-algoritme over het algemeen dezelfde structuur zouden moeten hebben.
  1. Door het toepassen van de strategie van het raadspel kan je nu een blok schrijven dat zegt wat:
    • De positie van een element in een gesorteerde lijst is.
    • Het aantal keer raden die nodig waren om het getal te vinden.
      • Geen Afbeelding Geen Afbeelding
    Als het getal meerdere keren in de lijst staat maakt het niet uit welke hij pakt.
  2. Bouw dan een positie in gesorteerde lijstblok dat de positie van een getal rapporteert in een lijst gesorteerd van laag naar hoog. Als het niet in de lijst staat, rapporteert het blok 0. (Opmerking: Deze taak is identiek aan de vorige alleen in plaats van dat het de positie "zegt", wordt die nu "gerapporteerd". )
    Geen Afbeelding
    Geen Afbeelding
  3. Vergelijk positie in gesorteerde lijst met positie in ongesorteerde lijst:
    1. Welke werkt sneller voor grote invoer?
    2. Welk blok bevat meer blokken?
  1. Maak een tabel die bijhoudt hoeveel keer gokken het kost om een getal te vinden in een gesorteerde lijst, afhankelijk van de lengte van de lijst als dat getal de laatste in de lijst blijkt te zijn.
    Lengte van de lijst Aantal gissen
    3
    7 3
    15
    63
    127
Terug Volgende