Python Binary Search

Denne artikkelen vil vise deg hvordan du bruker Python til å utføre en binær søketeknikk for å finne en enhets indeksposisjon i en liste.

Et binært søk er en måte å finne et bestemt element i en liste. La oss forestille oss at vi har en liste over ti tusen elementer og trenger å finne indeksposisjonen til en enkelt oppføring. Vi kan raskt finne indeksens plassering av et element ved hjelp av den binære søketeknikken. Andre søkealgoritmer eksisterer, men de mest omfattende ansatte er et binært søk. Sorter gjenstandene først hvis de ikke allerede er sortert.

Den binære søkealgoritmenes rekursive og iterative tilnærminger kan brukes til å finne elementposisjonen. Den rekursive strategien brukes etter skillet og erobre tilnærmingen. På denne måten utføres en funksjon til den finner et element i listen. For å oppdage et elements indeksplassering, gjentar den iterative teknikken gjentatte ganger et sett med ord. Denne prosessen er oppnådd ved hjelp av mens loopen. Fordi vi ikke trenger å søke i hver listeindeks, er binært søk mer effektivt enn lineært søk.

La oss starte med en grunnleggende forståelse av binær søk.

Eksempel 1:

Først bruker vi den iterative tilnærmingen for å implementere et binært søk. Vi sykler gjennom listen og gjentar en utsagnsekvens. Vi fortsetter å søke etter midtverdien til vi finner den.

Dette er en Python -implementering av den iterative binære søkefunksjonstilnærmingen. Hvis 'Search_num' er til stede i den gitte listen, returnerer den en; Ellers gir det -1. Vi konstruerte den binære søk () -funksjonen i dette programmet, som godtar to argumenter: en liste for å sortere og et tall for å søke. Vi har satt opp to variabler for å holde oversikt over listens laveste og største verdier. Den lave har en startverdi på 0, den høye har en verdi av Len (liste1) - 1, og midten har en verdi på 0. Mens Loop blir deretter skrevet med begrensningen som den laveste lik og er mindre enn den høyeste. Mens sløyfen vil iterere hvis tallet ikke er funnet ennå. Midtpunktet finnes i stundsløyfen. Så samsvarer vi med indeksverdien til antallet vi har lett etter. Hvis midt-indeksverdien er mindre enn 'søknummer', tildeler vi den til og hever midt-indeksverdien med en. Fokuset på søket endres til venstre. Angi midtverdien maksimalt hvis den er høy. Return midt hvis 'search_num' er lik midtverdien. Dette vil fortsette til det lave og høye er like og det lave er mindre enn det høye. Hvis vi kommer til slutten av funksjonen, vet vi at elementet ikke er i listen. Til påkallingsfunksjonen returnerer vi -1.

def binary_search (en, search_num):
lav = 0
Høy = Len (en) - 1
Midt = 0
mens du er lav <= high:
midt = (høy + lav) // 2
Hvis en [midt] search_num:
Høy = Midt - 1
ellers:
Returner midt
Retur -1
One = [19, 23, 43, 56, 65, 71, 80]
Search_num = 43
output = binary_search (en, search_num)
Hvis output != -1:
Print ("Element er på indeks", STR (Output))
ellers:
Print ("Element er ikke tilgjengelig på listen")

Her kan du se at det nødvendige antallet er funnet i indeksposisjon 2.

Eksempel 2:

La oss se på den rekursive binære søketilnærmingen. Rekursjonsmetoden kan brukes i binær søk. Vi lager en rekursiv funksjon som kaller seg til tilstanden er fornøyd. Foregående program er likt det før det. En rekursiv funksjon, så vel som dens grunntilstand, ble erklært. Vi beregner mellomnummeret som vi gjorde i forrige program. For å fortsette med det binære søket, brukte vi IF -uttalelsen. Det vil bli returnert hvis mellomverdien tilsvarer antallet vi leter etter. Hvis mellomverdien er under verdien, øker vi den med en og tildeler den til lav ved å bruke vår rekursive binære søk () -funksjon. Vi skrev hovedprogrammet vårt i den siste delen. Prosedyren for binær søk () krever nå 2 parametere, som er den eneste modifiseringen fra det forrige programmet. Manglende evne til den rekursive funksjonen til å tilordne startverdier til den lave, høye og midten er grunnen bak dette. Verdien for disse variablene vil bli tilbakestilt hver gang rekursjonen kalles.

def binary_search (en, lav, høy, search_num):
Hvis Low Search_num:
Return Binary_search (en, lav, midt - 1, search_num)
ellers:
Return Binary_search (One, Mid + 1, High, Search_num)
ellers:
Retur -1
One = [19, 23, 43, 56, 65, 71, 80]
Search_num = 65
output = binary_search (en, 0, len (en) -1, search_num)
Hvis Search_num != -1:
Print ("Element er på indeks", STR (Output))
ellers:
Print ("Element er ikke tilgjengelig på listen")

Den nødvendige verdien er på indeks 4, som du kan se i følgende bilde.

Eksempel 3:

Et annet eksempel på en binær søketeknikk, ofte kjent som en halvintervalt søkealgoritme, brukes til å finne en målverdi i en sortert matrise. Dette programmet returnerer sant hvis nummeret er plassert i listen.

def binary_search (my_list, search_num):
en = 0
finale = len (my_list) -1
funnet = falsk
mens (en<=final and not found):
midt = (en + finale) // 2
Hvis my_list [midt] == ​​search_num:
funnet = sant
ellers:
Hvis Search_numfinale = midt - 1
ellers:
en = midt + 1
retur funnet
Print (Binary_search ([1,2,3,4,5], 3))
Print (Binary_search ([11,22,33,44,55], 5)))

Nedenfor er utgangen.

Konklusjon:

Den mest effektive og raske tilnærmingen for å søke etter en oppføring i en liste er å bruke en binær søkealgoritme. Den hopper over den meningsløse analogien. Som navnet sier, er søket delt inn i to stykker. Det konsentrerer seg på siden av listen nærmest antallet vi leter etter. I den beste situasjonen er den binære søkealgoritmens kompleksitet O (1). Dette skjer når elementet vi søker vises i den første sammenligningen. Den verste og gjennomsnittlige sakskompleksiteten til det binære søket er O (LOGN). Det totale antall søk som kreves for å finne varen bestemmer dette. Ulike tilnærminger for å bestemme indeksposisjonen til et gitt antall er blitt diskutert.