Binaire zoekopdracht in Python: een complete gids voor efficiënt zoeken

Algemener gezegd is een algoritme een precieze reeks instructies die een computer volgt om een specifieke taak uit te voeren of een probleem op te lossen. Bekijk onze blogpost What is an Algorithm om te leren over de vele verschillende soorten algoritmen in machine learning.

Conceptoverzicht

Binaire zoekopdracht is een krachtig algoritme dat is ontworpen om efficiënt een waarde te vinden in een gesorteerde dataset. Het kernidee is eenvoudig: in plaats van elk element in de dataset één voor één te controleren, zoals bij lineaire zoekopdracht, verkleint binaire zoekopdracht het zoekbereik bij elke stap met de helft, waardoor het proces veel sneller gaat.

Zo werkt het:

1. Begin met het vergelijken van de doelwaarde met het middelste element van de dataset. De index voor de middelste waarde wordt berekend met de formule: middle = (low + high) / 2, waarbij low de index is van het eerste element in het huidige zoekbereik, en high de index van het laatste element.
2. Vergelijk de middelste waarde met het doel. Als de doelwaarde gelijk is aan het middelste element, heb je de index gevonden en is de zoekopdracht voltooid. Als de doelwaarde kleiner is dan het middelste element, gaat de zoekopdracht verder in de linkerhelft van de dataset. Als de doelwaarde groter is, gaat de zoekopdracht verder in de rechterhelft van de dataset.
3. Herhaal stap 1-2. Het zoekbereik wordt bij elke stap gehalveerd. Herhaal het proces totdat de doelwaarde is gevonden of het zoekbereik leeg is.

Het proces van binaire zoekopdracht. Afbeelding door de auteur

Hierboven staat een vereenvoudigd voorbeeld dat het concept achter binaire zoekopdracht laat zien.

Dit halveringsproces maakt binaire zoekopdracht zo efficiënt. Het is echter belangrijk op te merken dat de dataset gesorteerd moet zijn om correct te werken. Als de data niet gesorteerd is, functioneert het algoritme niet zoals bedoeld. 

Bekijk Data Structures: A Comprehensive Guide With Python Examples om meer te leren over verschillende soorten datastructuren waar je in kunt zoeken.

Belangrijke punten om te onthouden

De volgende punten benadrukken de kernprincipes van binaire zoekopdracht.

Efficiëntie

Binaire zoekopdracht is aanzienlijk sneller dan lineaire zoekopdracht, vooral bij grote datasets. Terwijl lineaire zoekopdracht een tijdscomplexiteit van O(n) heeft, wat betekent dat in het slechtste geval elk element gecontroleerd moet worden, is binaire zoekopdracht efficiënter. Het heeft een tijdscomplexiteit van O(log n), wat betekent dat de zoekruimte bij elke stap wordt gehalveerd, waardoor het aantal benodigde vergelijkingen aanzienlijk afneemt.

Voor een gedetailleerde uitleg over hoe algoritmen worden geëvalueerd, zie onze Big O Notation and Time Complexity Guide: Intuition and Math. Een optie is onze tutorial Analyzing Complexity of Code through Python.

Vereisten

Voor binaire zoekopdracht moet de dataset in oplopende of aflopende volgorde gesorteerd zijn. Dit is een vereiste omdat het algoritme vertrouwt op de volgorde van elementen om te bepalen in welke helft van de dataset vervolgens gezocht moet worden. Als de data niet gesorteerd is, kan binaire zoekopdracht de doelwaarde niet nauwkeurig lokaliseren.

Flexibiliteit

Binaire zoekopdracht kan worden geïmplementeerd met een iteratieve of recursieve aanpak. De iteratieve methode gebruikt lussen om het zoekbereik herhaaldelijk te halveren. De recursieve methode laat de functie zichzelf aanroepen met een kleiner zoekbereik. Deze flexibiliteit leent zich goed voor verschillende toepassingen.

Toepassingen in de echte wereld

Binaire zoekopdracht is een krachtig hulpmiddel. De efficiëntie waarmee het zoekbereiken snel verkleind worden, maakt het van onschatbare waarde, vooral bij grote datasets waar prestaties en snelheid cruciaal zijn. Laten we enkele specifieke toepassingen verkennen en zien hoe binaire zoekopdracht zich verhoudt tot andere algoritmen.

Databases

In databases wordt binaire zoekopdracht vaak gebruikt om snel records te vinden binnen gesorteerde velden, zoals het vinden van een specifieke gebruiker in een database die op gebruikers-ID is gesorteerd. Stel je een database met miljoenen records voor. Een lineaire zoekopdracht zou vereisen dat elk record één voor één wordt doorlopen, wat veel tijd kan kosten. In plaats daarvan kan binaire zoekopdracht het gewenste record snel aanwijzen door de zoekruimte systematisch te halveren, waardoor het aantal benodigde vergelijkingen sterk wordt verminderd.

Data science

Zoeken in grote, gesorteerde datasets is een veelvoorkomende taak in data science. Bij tijdreeksanalyse kan binaire zoekopdracht bijvoorbeeld worden gebruikt om specifieke tijdstempels te vinden binnen een gesorteerde reeks gebeurtenissen. In machine learning kunnen algoritmen voor binaire zoekopdracht worden gebruikt om hyperparameters te optimaliseren door de beste waarde binnen een bereik te vinden.

Computergrafiek

In computergrafiek wordt binaire zoekopdracht gebruikt in algoritmen waarbij precisie en snelheid nodig zijn. Een voorbeeld is raytracing, een rendertechniek die simuleert hoe licht met objecten interageert. Binaire zoekopdracht kan worden gebruikt om snel snijpunten tussen stralen en oppervlakken te vinden.

Bouwstenen voor complexe algoritmen

Binaire zoekopdracht is niet alleen op zichzelf nuttig; het dient ook als bouwsteen voor complexere algoritmen en datastructuren. Zo zijn zoekbomen, zoals binaire zoekbomen (BST’s), en gebalanceerde bomen, zoals AVL-bomen, gebaseerd op de principes van binaire zoekopdracht. Deze structuren maken efficiënt zoeken, invoegen en verwijderen mogelijk, waardoor ze nuttig zijn wanneer data dynamisch moet worden bijgewerkt en vaak moet worden doorzocht. Leer meer over deze bomen in AVL Tree: Complete Guide With Python Implementation.

Binaire zoekopdracht vs. andere zoekalgoritmen

Laten we verkennen hoe binaire zoekopdracht zich verhoudt tot twee andere veelvoorkomende zoekalgoritmen: lineaire zoekopdracht en hash lookup.

Lineaire zoekopdracht

Lineaire zoekopdracht is een eenvoudig algoritme dat elk element in een dataset sequentieel bekijkt. Het is aanzienlijk minder efficiënt dan binaire zoekopdracht, met een tijdscomplexiteit van O(n). Lineaire zoekopdracht vereist echter niet dat de data gesorteerd is, wat het in sommige scenario’s nuttig maakt.

Hash lookup

Hash lookup is een efficiënt algoritme dat wordt gebruikt om snel waarden in een dataset te vinden wanneer die waarden aan unieke sleutels zijn gekoppeld. Het werkt door een hashfunctie op de sleutel toe te passen, die een index berekent waar de bijbehorende waarde is opgeslagen in een hashtabel. Dit maakt vrijwel onmiddellijke opvraging van waarden mogelijk, vaak in O(1)-tijd. Hoewel hash lookup zeer snel is voor het vinden van specifieke elementen, vereist het extra geheugen om de hashtabel op te slaan en is het niet geschikt voor het zoeken binnen een bereik van waarden—een taak waarvoor binaire zoekopdracht beter geschikt is.

Binaire zoekopdracht implementeren in Python

Laten we een paar manieren verkennen om een eenvoudige binaire zoekopdracht in Python te implementeren. Maar eerst hebben we een eenvoudige dataset nodig om mee te werken en een doelwaarde om naar te zoeken. Stel dat we de volgende gesorteerde array en zoekdoel hebben:

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 56Mogelijk gemaakt door

Iteratieve methode

De iteratieve methode is misschien wel de meest rechttoe-rechtaan aanpak. Met deze methode gebruiken we een while-lus om het zoekinterval herhaaldelijk te halveren totdat we ons doel vinden. Deze methode wordt vaak geprezen om zijn duidelijkheid en efficiëntie.

Zo implementeer je binaire zoekopdracht iteratief:

def binary_search_iterative(arr, target):
    # Define the search bounds
    left, right = 0, len(arr) - 1  
    while left <= right:
        # Calculate the middle index
        mid = left + (right - left) // 2  
        # If the middle element is the target, return its index
        if arr[mid] == target:
            return mid  
        # If the target is bigger, narrow the search to the right half
        elif arr[mid] < target: 
            left = mid + 1  
        # If the target is smaller, narrow the search to the left half
        else: 
            right = mid - 1  
    # Return -1 if the target is not found
    return -1 
    
# Run the iterative function
result = binary_search_iterative(arr, target)
if result != -1:
    print(f"Iterative: Target found at index {result}")
else:
    print("Iterative: Target not found")Mogelijk gemaakt door

Laten we deze code van dichterbij bekijken:

• We beginnen met het instellen van ‘left’ en ‘right’ als de grenzen van de zoekruimte. Aanvankelijk is left 0 (het begin van de array), en ‘right’ is len(arr) - 1 (het einde van de array).

• In elke iteratie berekenen we de mid-index, die het midden van het huidige zoekinterval voorstelt. Dit gebeurt met de formule mid = left + (right - left) /2.

• Vervolgens vergelijken we het element op mid met target:

• Als ze overeenkomen, hebben we ons doel gevonden en geeft de functie mid terug.

• Als het element op mid kleiner is dan het doel, betekent dit dat het doel in de rechterhelft moet liggen, dus stellen we left in op mid + 1.

• Als het element op mid groter is dan het doel, moet het doel in de linkerhelft liggen, dus stellen we right in op mid - 1.

• De lus gaat door totdat het doel is gevonden of totdat left groter is dan right, wat betekent dat het doel niet in de array staat.

Recursieve methode

De recursieve methode voor binaire zoekopdracht is een andere manier om dit algoritme te implementeren. In plaats van een lus roept de functie zichzelf aan, waarbij de zoekgrenzen elke keer worden aangepast totdat het doel wordt gevonden of wordt vastgesteld dat het doel niet aanwezig is.

Zo implementeer je binaire zoekopdracht recursief:

def binary_search_recursive(arr, target, left, right):
    # If the search bounds cross, the target isn't in the array
    if left > right:  
        return -1
    # Calculate the middle index
    mid = left + (right - left) // 2 
    # If middle value equals the target, return the index
    if arr[mid] == target: 
        return mid  
    # If the target is bigger than the middle value, search in the right half
    elif arr[mid] < target: 
        return binary_search_recursive(arr, target, mid + 1, right)  
    # If the target is smaller than the middle value, search in the left half
    else: 
        return binary_search_recursive(arr, target, left, mid - 1)  

# Run the recursive function
result = binary_search_recursive(arr, target, 0, len(arr) - 1)

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

Laten we deze code van dichterbij bekijken:

• De recursieve functie start met dezelfde initiële grenzen left en right als de iteratieve functie.

• Eerst controleert ze of left groter is dan right. Zo ja, dan geeft de functie -1 terug, wat aangeeft dat het doel niet in de array staat.

• Anders berekent de functie de mid-index en vergelijkt het doel met het element op mid.

• Als het doel gelijk is aan het element op mid, geeft de functie mid terug.

• Als het doel groter is dan mid, roept de functie zichzelf recursief aan met bijgewerkte grenzen om in de rechterhelft te zoeken.

• Als het doel kleiner is dan mid, zoekt de functie in de linkerhelft.

• De recursie gaat door totdat het doel is gevonden of de zoekruimte is uitgeput.

Voor meer over recursieve functies, bekijk Understanding Recursive Functions in Python.

De ingebouwde bisect-module van Python gebruiken

De standaardbibliotheek van Python bevat de bisect-module, die voorgeïmplementeerde functies voor binaire zoekopdracht biedt. Deze module is zeer efficiënt en kan ons vaak tijd besparen ten opzichte van het bouwen van een eigen functie.

Zo gebruiken we de bisect-module om het doel in onze array te vinden:

# Import the bisect module
import bisect 

# Call the module and provide the array and the target value
index = bisect.bisect_left(arr, target) 

#Print results
if index < len(arr) and arr[index] == target:
    print(f"Bisect: Target found at index {index}")
else:
    print("Bisect: Target not found")Mogelijk gemaakt door

Laten we deze code van dichterbij bekijken:

• De functie bisect_left geeft de index terug waar het doel moet worden ingevoegd om de volgorde van de array te behouden. Als het doel op deze index wordt gevonden, betekent dit dat het doel in de array bestaat.

• Deze methode is vooral handig bij het werken met gesorteerde arrays en kan ook worden gebruikt om elementen in te voegen terwijl de gesorteerde volgorde behouden blijft.

• De bisect-module biedt ook andere functies zoals bisect_right en insort, die kunnen worden gebruikt om invoegpunten te vinden of om elementen direct in te voegen.

Tijds- en ruimtecomplexiteit

Wanneer we de efficiëntie van een algoritme bespreken, gebruiken we vaak Big O-notatie, weergegeven als O(x), om te beschrijven hoe de runtime of geheugenvraag groeit naarmate de omvang van de invoer toeneemt. Voor binaire zoekopdracht is de tijdscomplexiteit typisch O(log n). Dit betekent dat naarmate de dataset groeit, het aantal bewerkingen dat nodig is om het doel te vinden logaritmisch toeneemt, waardoor binaire zoekopdracht ook bij grote datasets efficiënt is.

De iteratieve methode van binaire zoekopdracht heeft een tijdscomplexiteit van O(log n) omdat het zoekinterval bij elke iteratie wordt gehalveerd. De ruimtecomplexiteit is O(1) omdat het een constante hoeveelheid extra geheugen gebruikt, en slechts een paar variabelen nodig heeft om de zoekgrenzen en het middelste element bij te houden.

De recursieve methode heeft om dezelfde reden ook een tijdscomplexiteit van O(log n). De ruimtecomplexiteit is echter O(log n) vanwege de ruimte die nodig is om de call stack voor elke recursieve aanroep te onderhouden. Omdat elke recursieve aanroep een laag aan de stack toevoegt, is de diepte van de recursie evenredig met het aantal halveringsstappen, wat logaritmisch is ten opzichte van de grootte van de dataset.

Hoewel beide methoden qua tijd efficiënt zijn, is de iteratieve aanpak zuiniger in geheugen. Daarom gebruikt de bisect-module onder de motorkap een iteratieve aanpak. Persoonlijk geef ik om die reden ook de voorkeur aan de iteratieve aanpak. Voor sommigen kan de recursieve aanpak echter intuïtiever zijn en minder regels code vereisen.

Veelvoorkomende valkuilen en hoe ze te vermijden

Bij het gebruik van een binaire zoekopdracht zijn er een paar veelvoorkomende valkuilen om op te letten. Deze kunnen de correctheid en efficiëntie van je algoritme beïnvloeden, dus het is belangrijk om ze te kennen.

Ten eerste is binaire zoekopdracht afhankelijk van een gesorteerde dataset. Als de data niet gesorteerd is, zal binaire zoekopdracht niet correct functioneren; het kan onjuiste resultaten teruggeven of helemaal falen. Het is daarom essentieel om onze dataset te sorteren voordat we binaire zoekopdracht toepassen. Als sorteren niet haalbaar is, is binaire zoekopdracht niet het juiste hulpmiddel.

Een veelvoorkomend probleem zijn off-by-one-fouten. Deze treden op wanneer de indexberekeningen net niet kloppen, wat mogelijk leidt tot oneindige lussen of het niet kunnen vinden van de doelwaarde. Dit kan gebeuren als de berekening van het middenpunt of het aanpassen van de grenzen niet precies wordt afgehandeld. Zorg ervoor dat de berekeningen voor de middelste index kloppen en dat de grenzen na elke vergelijking correct worden bijgewerkt. Denk eraan: indexwaarden in Python beginnen bij 0, niet bij 1.

Een andere uitdaging om rekening mee te houden als je binaire zoekopdracht recursief gebruikt, zijn problemen met recursiediepte. In Python is er een limiet aan het aantal recursieve aanroepen om buitensporig geheugengebruik te voorkomen. Als je dataset erg groot is, kan diepe recursie deze limiet overschrijden, wat een stack overflow veroorzaakt. Om dit te beperken, overweeg de iteratieve aanpak voor binaire zoekopdracht, die niet lijdt onder beperkingen in recursiediepte. Als recursie de voorkeur heeft of nodig is, kun je mogelijk de recursielimiet verhogen met sys.setrecursionlimit(), maar doe dit met voorzichtigheid om andere mogelijke problemen te vermijden.

Conclusie

Binaire zoekopdracht is een krachtig en efficiënt algoritme dat in de toolkit van elke Python-developer thuishoort. Of het nu iteratief of recursief wordt geïmplementeerd, het biedt een aanzienlijk prestatievoordeel ten opzichte van lineaire zoekopdracht, vooral bij grote datasets. Voor meer, bekijk de skill track DataCamp’s Python Programming of de interactieve cursus Software Engineering Principles in Python.