Lineair zoeken in Python: een beginnersgids met voorbeelden

Als het om zoekalgoritmes gaat, is lineair zoeken een van de simpelste. Als je ooit een lijst met items één voor één hebt doorgenomen tot je vond wat je zocht, dan heb je al een lineaire zoekactie uitgevoerd!

Naast dat het makkelijk te begrijpen is, is lineair zoeken nuttig omdat het werkt op ongesorteerde data, in tegenstelling tot sommige andere zoekalgoritmes. Deze veelzijdigheid maakt het een bruikbare optie in situaties waarin sorteren van data niet mogelijk is. In deze tutorial gebruik ik Python, dus als je, voordat we beginnen, je geheugen over Python wilt opfrissen, bekijk dan de skill track Python Programming.

Wat is lineair zoeken?

Lineair zoeken is een algoritme dat een specifieke waarde in een lijst lokaliseert door elk element één voor één te controleren. Het begint bij het eerste item, vergelijkt dat met de doelwaarde en gaat vervolgens door de lijst heen totdat het de doelwaarde vindt of het einde van de lijst bereikt. Het is een eenvoudig en intuïtief algoritme.

Lineair zoeken heeft niet nodig dat de data gesorteerd is om te werken, dus wordt het vooral gebruikt bij ongesorteerde datasets. Dit is handig in situaties waarin sorteren niet praktisch is of je met ruwe data werkt. Deze voordeel heeft echter een prijs: het is niet zo efficiënt als andere algoritmes die wel presorteerde data vereisen.

Lineair zoeken is ideaal wanneer je met relatief kleine datasets werkt of wanneer het niet haalbaar is om de data te sorteren. Het onderstaande diagram geeft een vereenvoudigde uitleg.

Kiezen voor lineair zoeken

Laten we kijken naar de voordelen en ook één duidelijk nadeel: 

Waarom kiezen voor lineair zoeken?

Wat mij betreft heeft lineair zoeken drie duidelijke voordelen:

Als eenvoud de doorslag geeft

Een van de grootste voordelen van lineair zoeken is de eenvoud. Het algoritme is makkelijk te begrijpen en te implementeren. Je hoeft je geen zorgen te maken over complex sorteren of het opsplitsen van data. Begin gewoon aan het begin van de lijst en controleer elk element totdat je vindt wat je zoekt.

Als je geen tijd hebt om te sorteren

In tegenstelling tot andere zoekalgoritmes, zoals binair zoeken, vereist lineair zoeken niet dat de dataset gesorteerd is. Dat maakt het perfect wanneer je snel iets wilt vinden.

Als je flexibiliteit nodig hebt

Een ander voordeel van lineair zoeken is dat het veelzijdig is. Het werkt niet alleen met arrays, maar ook met andere Python-datastructuren, zoals gelinkte lijsten. Zolang je de elementen sequentieel kunt benaderen, kan lineair zoeken het werk doen. Het is flexibel genoeg om verschillende datatypen aan te kunnen, van getallen tot strings en zelfs objecten.

Waarom toch even twijfelen over lineair zoeken?

Er is een punt om rekening mee te houden:

Als efficiëntie telt

Het grootste nadeel van lineair zoeken is de inefficiëntie, vooral bij grote datasets. De tijdcomplexiteit is O(n), wat betekent dat je in het slechtste geval elk element in de lijst moet controleren! Dat kan alles flink vertragen als je met duizenden of miljoenen items werkt. Voor kleine datasets kan deze inefficiëntie echter verwaarloosbaar zijn.

Een lineair-zoekalgoritme implementeren in Python

In Python zijn er twee gangbare manieren om lineair zoeken te schrijven: de iteratieve methode en de recursieve methode. Om beide methodes te demonstreren, maken we eerst een eenvoudige dataset van 100 unieke getallen.

numbers = [12, 7, 19, 3, 15, 25, 8, 10, 42, 56, 77, 23, 89, 65, 33, 99, 14, 2, 37, 81,
           48, 64, 22, 91, 6, 40, 59, 87, 28, 53, 74, 9, 16, 39, 71, 93, 54, 32, 61, 27,
           35, 18, 49, 68, 83, 46, 57, 29, 95, 11, 26, 44, 78, 5, 66, 73, 41, 85, 31, 50,
           20, 63, 88, 34, 90, 60, 67, 4, 52, 36, 62, 80, 21, 84, 98, 13, 45, 69, 30, 38,
           47, 17, 92, 55, 70, 76, 82, 24, 43, 1, 100, 58, 96, 75, 97, 94, 86, 72, 51, 79]Mogelijk gemaakt door

Iteratieve methode

De iteratieve aanpak is waarschijnlijk de makkelijkste manier om lineair zoeken te begrijpen. Je loopt door de lijst en controleert elk element totdat je de doelwaarde vindt of het einde bereikt.

Eerst maken we onze functie:

1. We lopen elk element in de lijst arr langs.

2. We vergelijken elk element met de doelwaarde.

3. Als we een match vinden, geven we de index terug waar de doelwaarde is gevonden.

4. Als we de lus eindigen zonder de doelwaarde te vinden, geven we 1 terug om aan te geven dat het element niet aanwezig is.

def linear_search_iterative(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return the index if the target is found
    return -1  # Return -1 if the target is not foundMogelijk gemaakt door

Vervolgens draaien we onze functie op onze dataset en printen we het resultaat:

# Run the function on the numbers list
target = 91
index = linear_search_iterative(numbers, target)

if index != -1:
    print(f"Target {target} found at index {index}")
else:
    print(f"Target {target} not found!")Mogelijk gemaakt door

Als we deze code uitvoeren, vinden we de doelwaarde op het 23e element.

Recursieve methode

De recursieve methode gebruikt een functie die zichzelf aanroept om door de lijst te zoeken. Elke recursieve aanroep verwerkt één element tegelijk en gaat vervolgens door naar het volgende element. Dit gaat door totdat de doelwaarde is gevonden of het einde van de lijst is bereikt.

Laten we onze recursieve functie maken:

1. We beginnen met het eerste element (op index 0) te controleren.
2. Als de doelwaarde overeenkomt, geven we de index terug.
3. Als de doelwaarde niet overeenkomt, roepen we dezelfde functie recursief aan, maar verhogen we de index met 1 om het volgende element te controleren.
4. De recursie gaat door totdat we de doelwaarde vinden of het einde van de lijst bereiken.

def linear_search_recursive(arr, target, index=0):
    if index >= len(arr):  # Base case: we've checked all elements
        return -1
    if arr[index] == target:  # Base case: target found
        return index
    return linear_search_recursive(arr, target, index + 1)  # Recursive case: check next elementMogelijk gemaakt door

We kunnen dezelfde code als hierboven gebruiken om deze functie uit te voeren en die geeft voor onze doelwaarde dezelfde index terug: 23.

Houd er rekening mee dat deze aanpak meer geheugen gebruikt omdat elke recursieve aanroep een nieuwe laag toevoegt aan de call stack. Bekijk Understanding Recursive Functions in Python voor een nadere blik op recursie.

Tijd- en ruimtecomplexiteit

Een manier om de efficiëntie van een algoritme te beoordelen, is te kijken naar de tijd- en ruimtecomplexiteit. Bekijk de tutorial Analyzing Complexity of Code through Python voor een overzicht van de verschillende manieren om de complexiteit van een algoritme te meten.

Tijdcomplexiteit

De tijdcomplexiteit van een algoritme verwijst naar hoe de benodigde tijd toeneemt naarmate de grootte van de invoer groeit. De tijdcomplexiteit van lineair zoeken is O(n), waarbij n het aantal elementen in de lijst is. Dit betekent dat het algoritme in het slechtste geval elk element moet controleren voordat het de doelwaarde vindt (of vaststelt dat de doelwaarde niet in de lijst staat). Dit is behoorlijk inefficiënt, zeker voor grote datasets. Daarom werkt lineair zoeken het beste bij kleinere, ongesorteerde datasets die we maar één keer hoeven te doorzoeken.

Ruimtecomplexiteit

De ruimtecomplexiteit van een algoritme meet hoeveel geheugen het nodig heeft naarmate de invoer groeit. De ruimtecomplexiteit van het lineair-zoekalgoritme hangt af van de methode die we gebruiken. Voor de iteratieve methode is de ruimtecomplexiteit O(1), wat betekent dat het algoritme een constante hoeveelheid geheugen nodig heeft, ongeacht de grootte van de inputlijst. Dit komt doordat de iteratieve versie geen extra geheugen vereist, afgezien van de inputlijst en een paar variabelen om de huidige index bij te houden.

Voor de recursieve methode is de ruimtecomplexiteit O(n), wat betekent dat de benodigde hoeveelheid geheugen lineair toeneemt met de grootte van de inputlijst. Dit komt door de recursieve functieaanroepen, die voor elk element in de lijst lagen toevoegen aan de call stack. Een grotere lijst vereist meer geheugen om die aanroepen op te slaan, waardoor de recursieve aanpak minder ruimte-efficiënt is.

Toepassingen van lineair zoeken in de praktijk

Hoewel lineair zoeken niet het meest efficiënte algoritme is voor grote datasets, heeft het in veel scenario’s praktische toepassingen. Laten we enkele situaties bekijken waarin lineair zoeken het beste gereedschap is.

Kleine datasets waarbij sorteren niet praktisch is

Lineair zoeken is vaak mijn go-to wanneer ik met kleine datasets werk die de tijd of middelen voor sorteren niet waard zijn. In zulke gevallen kan de eenvoud van lineair zoeken efficiënter zijn dan de overhead van sorteren voor complexere zoekalgoritmes.

De eerste voorkomens van een doelwaarde vinden

Een ander veelvoorkomend gebruik van lineair zoeken is wanneer je het eerste voorkomen van een doelwaarde moet vinden. Omdat lineair zoeken de lijst element voor element doorloopt, vindt het van nature de eerste instantie van de doelwaarde en retourneert het de positie. Dit is vooral handig bij bijvoorbeeld het doorzoeken van een string naar het eerste voorkomen van een teken.

Wanneer minimale voorbereiding nodig is

Soms maakt de eenvoud van lineair zoeken het de beste optie. Bijvoorbeeld wanneer je snel data wilt doorzoeken die je niet verwacht te hergebruiken, of wanneer je vlug een ruwe schatting nodig hebt: de minimale voorbereiding bij lineair zoeken kan je tijd besparen.

Lineair zoeken vs. andere zoekalgoritmes

Lineair zoeken is slechts één van de vele zoekalgoritmes. Laten we twee andere gangbare zoekmethodes bekijken: binair zoeken en hash-lookup.

Lineair zoeken vs. binair zoeken

Binair zoeken is een algoritme dat de positie van een doelwaarde in een gesorteerde array vindt door het zoekinterval herhaaldelijk te halveren. Het heeft een tijdcomplexiteit van O(log n) en is daarmee veel efficiënter dan lineair zoeken. Het werkt echter alleen op gesorteerde data. Wanneer je dataset gesorteerd is, is binair zoeken bijna altijd de betere keuze omdat het de zoekruimte bij elke stap halveert, waardoor het aantal vergelijkingen drastisch afneemt.

Lineair zoeken kan geschikter zijn wanneer je data ongesorteerd is, aangezien lineair zoeken werkt op elke dataset, gesorteerd of niet. Met een tijdcomplexiteit van O(n) is lineair zoeken echter veel minder efficiënt op gesorteerde datasets.

Lineair zoeken vs. hash-lookup

Hash-lookup is een methode die een hashtabel gebruikt om snel een element te vinden. Met een tijdcomplexiteit van O(1) is het aanzienlijk sneller dan lineair of binair zoeken. Deze snelheid heeft echter een prijs: je moet eerst een hashtabel opbouwen, wat tijd en extra geheugen kost. Hash-lookups werken het beste wanneer je meerdere keren door grote datasets moet zoeken, zodat de initiële setup zich op termijn terugbetaalt.

Daarentegen vereist lineair zoeken geen voorbereiding, waardoor het een meer rechttoe-rechtaan optie is. Het is de betere keuze wanneer je maar één keer of slechts een paar keer hoeft te zoeken en de extra tijd voor het opzetten van een hashtabel niet te rechtvaardigen is. Lineair zoeken kan ook ruimte-efficiënter zijn omdat je geen hashtabel hoeft op te slaan om het algoritme te gebruiken.

Veelvoorkomende valkuilen en hoe ze te vermijden

Hoewel lineair zoeken een rechttoe-rechtaan algoritme is, zijn er een paar veelgemaakte fouten om op te letten.

Off-by-one-fouten bij iteratie

Een van de meest voorkomende fouten bij het implementeren van lineair zoeken is een off-by-one-fout. Dit wordt veroorzaakt door de iteratie op de verkeerde index te starten of te stoppen. Het is belangrijk te onthouden dat Python-lijsten nulgebaseerd zijn, wat betekent dat het eerste element index 0 heeft. Als je dat vergeet, kun je per ongeluk het eerste element overslaan of één stap te ver itereren, wat leidt tot onjuiste resultaten of fouten.

De geretourneerde index verkeerd begrijpen

Een andere veelvoorkomende valkuil is verkeerd begrijpen wat de functie retourneert wanneer de doelwaarde niet in de lijst voorkomt. Volgens conventie retourneren veel zoekalgoritmes (inclusief lineair zoeken) -1 om aan te geven dat de doelwaarde niet aanwezig is. Sommige beginners gaan er echter van uit dat None, False of een andere waarde wordt teruggegeven, wat tot verwarring kan leiden bij het interpreteren van de resultaten.

Wanneer je lineair zoeken niet moet gebruiken

Zoals eerder genoemd, wordt lineair zoeken al snel inefficiënt voor grotere datasets. Om die reden is het het best voorbehouden aan kleine, ongesorteerde datasets of snelle zoekacties die je maar één keer uitvoert.

Conclusie

Als een van de meest rechttoe-rechtaan zoekmethodes controleert lineair zoeken elk element in een lijst sequentieel, wat het makkelijk maakt om te begrijpen en te implementeren. Lineair zoeken is een betrouwbare keuze voor snelle, eenmalige zoekacties op kleine datasets, vooral wanneer de data ongesorteerd is.

Als je geïnteresseerd bent in zoekalgoritmes, bekijk dan mijn andere artikelen in deze serie: Binary Search in Python, Depth-First Search in Python en Breadth-First Search in Python. Mogelijk ben je ook geïnteresseerd in AVL Tree: Complete Guide With Python Implementation en Introduction to Network Analysis in Python als meer gevorderde onderwerpen.