Binær søgning i Python: En visuel introduktion

Velkommen

I denne artikel lærer du, hvordan Binary Search-algoritmen fungerer bag kulisserne, og hvordan du kan implementere den i Python.

Især vil du lære:

  • Hvordan algoritmen fungerer bag kulisserne for at finde et målelement.
  • Hvordan dets Python-implementering fungerer linje for linje.
  • Hvorfor det er en meget effektiv algoritme sammenlignet med Lineær søgning.
  • Dens fordele og krav.

Lad os begynde! ✨

? Introduktion til binær søgning

Denne algoritme bruges til at finde et element i en ordnet sekvens (for eksempel: en liste, tuple eller streng).

Krav

For at anvende Binary Search-algoritmen til en sekvens skal sekvensen allerede sorteres i stigende rækkefølge. Ellers finder algoritmen ikke det rigtige svar. Hvis det gør det, vil det ske ved et rent tilfælde.

Tip: Du kan sortere sekvensen, inden du anvender binær søgning med en sorteringsalgoritme, der opfylder dine behov.

Indgang og udgang

Algoritmen (implementeret som en funktion) har brug for disse data:

  • En ordnet række af elementer (for eksempel: liste, tuple, streng).
  • Det målelement, som vi søger efter.

Det returnerer indekset for det element, du leder efter, hvis det findes. Hvis elementet ikke findes, returneres -1.

Effektivitet

Det er meget effektivt sammenlignet med Lineær søgning (søgning efter et element en efter en, startende fra det første), fordi vi er i stand til at "kassere" halvdelen af ​​listen på hvert trin.

Lad os begynde at dykke ned i denne algoritme.

? Visuel gennemgang

Vi anvender algoritmen for binær søgning på denne liste:

? Tip: Bemærk, at listen allerede er sorteret. Det omfattede indekserne som en visuel reference.

Mål

Vi vil finde indekset for heltal 67 .

Interval

Lad os lade som om vi er algoritmen. Hvordan starter vi processen?

Vi starter med at vælge de to grænser for intervallet, hvor vi vil søge. Vi vil søge i hele listen, så vi vælger indeks 0som den nedre grænse og indeks 5som den øvre grænse:

Mellemelement

Nu skal vi finde indekset for det midterste element i dette interval. Vi gør dette ved at tilføje den nedre grænse og den øvre grænse og dividere resultatet med 2 ved hjælp af heltal.

I dette tilfælde (0 + 5)//2er 2fordi resultatet af 5/2er 2.5og heltal division afkorter decimal del.

Så det midterste element er placeret ved indeks 2 , og det midterste element er tallet 6 :

Sammenligninger

Nu skal vi begynde at sammenligne mellemelementet med vores målelement for at se, hvad vi skal gøre næste.

Vi spørger:

Er det midterste element lig med det element, vi leder efter?

6 == 67 # False

Nej, det er det ikke.

Så vi spørger:

Er det midterste element større end det element, vi leder efter?

6 > 67 # False

Nej, det er det ikke.

det midterste element er mindre end det element, vi leder efter.

6 < 67 # True

Kassér elementer

Da listen allerede er sorteret, fortæller dette os noget meget vigtigt. Det fortæller os, at vi kan "kassere" den nederste halvdel af listen, fordi vi ved, at alle de elementer, der kommer før det midterste element, vil være mindre end det element, vi leder efter, så vores målelement er ikke der.

Start igen - Vælg grænserne

Hvad gør vi nu? Vi har kasseret elementerne, og cyklussen gentages igen.

Vi er nødt til at vælge grænserne for det nye interval (se nedenfor). Men bemærk, at den øvre grænse holdes intakt, og kun den nedre grænse ændres.

Dette skyldes, at det element, vi leder efter, kunne være i den øverste halvdel af listen. Den øvre grænse holdes intakt, og den nedre grænse ændres til at "krympe" intervallet til et interval, hvor vores målelement kunne findes.

? Tip: Hvis den midterste element havde været større end det element, vi er på udkig efter, den øvre grænse ville være blevet ændret, og den nedre grænse ville have været holdt intakt. På denne måde vil vi kassere den øverste halvdel af listen og fortsætte søgningen i den nederste halvdel.

Mellemelement

Nu skal vi finde indekset for det midterste element ved at tilføje den nedre grænse til den øvre grænse og dividere resultatet med 2 ved hjælp af heltal.

Resultatet af (3+5)//2er 4, så det midterste element er placeret ved indeks,4 og det midterste element er 67 .

Sammenligninger

Vi spørger:

Er det midterste element lig med det element, vi leder efter?

67 == 67 # True

Ja det er! Så vi har fundet elementet i indeks 4 . Værdien 4 returneres, og algoritmen blev gennemført med succes.

? Tip: Hvis ikke var blevet fundet elementet, processen ville have fortsat, indtil det interval var ikke længere gyldig. Hvis elementet ikke var fundet i hele listen, ville -1 være returneret.

? Gennemgang af kode

Nu hvor du har en visuel intuition af, hvordan algoritmen fungerer bag kulisserne, lad os dykke ned i den iterative Python-implementering ved at analysere den linje for linje:

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

Header

Her har vi funktionsoverskriften:

def binary_search(data, elem):

Det kræver to argumenter:

  • Den ordnede rækkefølge af elementer (for eksempel: liste, tuple eller streng).
  • Det element, som vi ønsker at finde.

Indledende interval

Den næste linje indstiller de første nedre og øvre grænser:

low = 0 high = len(data) - 1

Den indledende nedre grænse er indeks, 0og den oprindelige øvre grænse er det sidste indeks i sekvensen.

Sløjfe

Vi gentager processen, mens der er et gyldigt interval, mens den nedre grænse er mindre end eller lig med den øvre grænse.

while low <= high:

? Tip: Husk, at grænserne er indekser.

Mellemelement

På hver iteration er vi nødt til at finde indekset for det midterste element. For at gøre dette tilføjer vi de nedre og øvre grænser og deler resultatet med 2 ved hjælp af heltal.

middle = (low + high)//2

? Tip: Vi bruger heltalsdeling, hvis listen eller intervallet indeholder et lige antal elementer. For eksempel, hvis listen havde 6 elementer, og vi ikke brugte heltal, middleville resultatet være, (0 + 5)/2hvilket er 2.5. Et indeks kan ikke være en float, så vi afkorter decimaldelen ved hjælp af //og vælger elementet ved indeks 2.

Sammenligninger

Med disse betingelser (se nedenfor) bestemmer vi, hvad vi skal gøre afhængigt af værdien af ​​det midterste element data[middle]. Vi sammenligner det med det målelement, som vi leder efter.

if data[middle] == elem: return middle elif data[middle] > elem: high = middle - 1 else: low = middle + 1

Der er tre muligheder:

  • Hvis det midterste element er lig med det element, vi leder efter, returnerer vi indekset med det samme, fordi vi fandt elementet.
if data[middle] == elem: return middle
  • Hvis det midterste element er større end det element, vi leder efter, tildeler vi den øvre grænse igen, fordi vi ved, at målelementet er i den nederste halvdel af listen.
elif data[middle] > elem: high = middle - 1
  • Ellers er den eneste mulighed tilbage, at det midterste element er mindre end det element, vi leder efter, så vi tildeler den nedre grænse igen, fordi vi ved, at målelementet er i den øverste halvdel af listen.
else: low = middle + 1

Element ikke fundet

Hvis løkken er afsluttet uden at finde elementet, returneres værdien -1.

return -1

og vi har den endelige implementering af Binary Search-algoritmen:

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

? Særtilfælde

Dette er nogle særlige tilfælde, som du kan finde, når du begynder at arbejde med denne algoritme:

Gentagne elementer

Hvis det element, du leder efter, gentages i sekvensen, afhænger det returnerede indeks af antallet af elementer og af rækkefølgen af ​​operationer, som algoritmen udfører på sekvensen.

>>> >>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 7) 4 

Element ikke fundet

Hvis elementet ikke findes, returneres -1.

>>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 8) -1

Tom sekvens

Hvis sekvensen er tom, returneres -1.

>>> b = [] >>> binary_search(b, 8) -1

Usorteret sekvens

Hvis sekvensen ikke er sorteret, er svaret ikke korrekt. At få det korrekte indeks er rent tilfældigt, og det kan skyldes rækkefølgen af ​​elementerne i sekvensen og rækkefølgen af ​​operationer, der udføres af algoritmen.

Dette eksempel returnerer det korrekte resultat:

>>> b = [5, 7, 3, 0, -9, 2, 6] >>> binary_search(b, 6) 6

Men denne gør det ikke:

>>> b = [5, 7, 3, 0, -9, 2, 10, 6] >>> binary_search(b, 6) -1

? Tip: Tænk over, hvorfor det første eksempel returnerer det korrekte resultat. Tip: Det er rent tilfældigt, at rækkefølgen af ​​elementerne tilfældigvis får algoritmen til at nå det korrekte indeks, men trin-for-trin-processen evaluerer 0derefter 2og endelig 6. I dette særlige tilfælde findes det korrekte indeks for dette bestemte element, selvom sekvensen ikke er sorteret.

? Et mere komplekst eksempel

Nu hvor du er mere fortrolig med algoritmen og dens Python-implementering, har vi her et mere komplekst eksempel:

Vi vil finde indekset for elementet 45 på denne liste ved hjælp af binær søgning:

Første gentagelse

Nedre og øvre grænse er valgt:

Det midterste element ( 26 ) er valgt:

Men det midterste element ( 26 ) er ikke det element, vi leder efter, det er mindre end 45 :

Anden gentagelse

Så vi kan kassere alle de elementer, der er mindre end det midterste element og vælge nye grænser. Den nye nedre grænse ( 27 ) er elementet placeret umiddelbart til højre for det forrige midterste element:

? Tip: Husk, at listen allerede er sorteret.

Det nye mellemelement ( 30 ) er valgt:

Det midterste element ( 30 ) er ikke det element, vi leder efter, det er mindre end 45 :

Tredje gentagelse

Vi kan kassere de elementer, der er mindre end eller lig med 30, som ikke allerede er kasseret. Den nedre grænse opdateres til 32 :

Her har vi en interessant sag: det midterste element er et af grænserne for det aktuelle interval, fordi det (7+8)//2er 7.

Det midterste element ( 32 ) er ikke det element, vi leder efter ( 45 ), det er mindre.

Fjerde gentagelse

Vi kan kassere de elementer, der er mindre end eller lig med 32, som ikke allerede er kasseret.

Her har vi en anden meget interessant sag: intervallet har kun et element.

? Tip: Dette interval er gyldigt, fordi vi skrev denne betingelse while high <= low:, som inkluderer intervaller, hvor indekset for den nedre grænse er lig med indekset for den øvre grænse.

Det midterste element er det eneste element i intervallet, fordi det (8+8)//2er 8, så indekset for det midterste element er 8, og det midterste element er 45 .

Nu er det midterste element det element, vi leder efter, 45 :

Så værdien 8 (indekset) returneres:

>>> binary_search([1, 3, 7, 15, 26, 27, 30, 32, 45], 45) 8

? Ekstra øvelse

Hvis du gerne vil have lidt ekstra øvelse med denne algoritme, så prøv at forklare, hvordan algoritmen fungerer bag kulisserne, når den anvendes på denne liste for at finde heltal 90 :

[5, 8, 15, 26, 38, 56]
  • Hvad sker der trin for trin?
  • Hvilken værdi returneres?
  • Er elementet fundet?

Jeg håber virkelig, du kunne lide min artikel og fandt det nyttigt. Nu kan du implementere Binary Search-algoritmen i Python. Tjek mit online-kursus "Python-søgning og sorteringsalgoritmer: en praktisk tilgang". Følg mig på Twitter. ⭐️