Binaarotsing Pythonis: visuaalne sissejuhatus

Tere tulemast

Sellest artiklist saate teada, kuidas binaarotsingu algoritm kulisside taga töötab ja kuidas saate seda Pythonis rakendada.

Eelkõige õpid:

  • Kuidas algoritm toimib kulisside taga sihtelemendi leidmiseks.
  • Kuidas selle Pythoni juurutamine rea kaupa töötab?
  • Miks see on lineaarse otsinguga võrreldes väga tõhus algoritm?
  • Selle eelised ja nõuded.

Alustagem! ✨

? Binaarotsingu tutvustus

Seda algoritmi kasutatakse elemendi leidmiseks järjestatud järjestuses (näiteks loend, dupleks või string).

Nõuded

Binaarotsingu algoritmi jadale rakendamiseks tuleb järjestus juba järjestada kasvavas järjekorras. Vastasel juhul ei leia algoritm õiget vastust. Kui see juhtub, siis täiesti juhuslikult.

? Nõuanne. Enne kahendotsingu rakendamist saate järjestuse järjestada teie vajadustele vastava sorteerimisalgoritmiga.

Sisend ja väljund

Algoritm (rakendatud funktsioonina) vajab neid andmeid:

  • Järjestatud elementide jada (näiteks: loend, dupleks, string).
  • Sihtelemend, mida otsime.

See tagastab otsitava elemendi indeksi , kui see on leitud. Kui elementi ei leitud, tagastatakse -1.

Tõhusus

See on lineaarse otsinguga (elemendi otsimine ükshaaval, alustades esimesest) võrreldes väga tõhus, kuna oleme võimelised igal sammul poole loendist ära viskama.

Alustame sukeldumist sellesse algoritmi.

? Visuaalne ülevaade

Rakendame kahendotsingu algoritmi selles loendis:

? Nõuanne. Pange tähele, et loend on juba sorditud. See sisaldas visuaalse viitena indekseid.

Eesmärk

Soovime leida täisarvu 67 indeksi .

Intervall

Teeskleme, et oleme algoritm. Kuidas me protsessi alustame?

Alustame selle intervalli kahe piiri valimisega, kust soovime otsida. Soovime otsida kogu loendist, nii et valime 0alumise piirina indeksi 5ja ülemise piiri:

Keskmine element

Nüüd peame selles intervallis leidma keskmise elemendi indeksi. Teeme selle, lisades alumise ja ülemise piiri ning jagades tulemuse 2-ga täisarvude jagamise abil.

Sel juhul (0 + 5)//2on 2see tingitud sellest, et jagamise tulemus 5/2on 2.5ja täisarv kärbib kümnendosa.

Nii et keskmine element asub indeksis 2 ja keskmine element on number 6 :

Võrdlused

Nüüd peame alustama keskmise elemendi võrdlemist meie sihtelemendiga, et näha, mida peame edasi tegema.

Me küsime:

Kas keskmine element on võrdne otsitava elemendiga?

6 == 67 # False

Ei ole.

Seega küsime:

Kas keskmine element on suurem kui otsitav element?

6 > 67 # False

Ei ole.

Nii et keskmine element on väiksem kui meie otsitav element.

6 < 67 # True

Visake elemendid minema

Kuna loend on juba sorteeritud, ütleb see meile midagi äärmiselt olulist. See ütleb meile, et me võime loendi alumise poole "ära visata", sest me teame, et kõik elemendid, mis tulevad enne keskmist elementi, on väiksemad kui meie otsitavad elemendid, nii et meie sihtelementi pole olemas.

Alusta uuesti - valige piirid

Mida me edasi teeme? Oleme elemendid kõrvale heitnud ja tsüklit korratakse uuesti.

Peame valima uue intervalli piirid (vt allpool). Kuid pange tähele, et ülemist piiri hoitakse puutumatuna ja muudetakse ainult alumist piiri.

Seda seetõttu, et otsitav element võiks olla loendi ülemisel poolel. Ülemine piir hoitakse puutumatuna ja alumine piir muudetakse intervalli "kokkutõmbamiseks" selliseks intervalliks, kus meie sihtelemendi võiks leida.

? Nõuanne: kui keskmine element oleks olnud suurem kui meie otsitav element, oleks ülemist piiri muudetud ja alumist piiri puutumata. Sel viisil loobuksime loendi ülemisest poolest ja jätkaksime otsimist alumises osas.

Keskmine element

Nüüd peame leidma keskmise elemendi indeksi, lisades alumise piiri ülemisele piirjoonele ja jagades tulemuse 2-ga täisarvude jagamise abil.

Tulemuseks (3+5)//2on 4, nii et keskmine element asub indeksis4 ja keskmine element on 67 .

Võrdlused

Me küsime:

Kas keskmine element on võrdne otsitava elemendiga?

67 == 67 # True

Jah see on! Nii leidsime elemendi indeksist 4 . Väärtus 4 tagastatakse ja algoritm on edukalt lõpule viidud.

? Nõuanne: kui elementi ei oleks leitud, oleks protsess jätkunud seni, kuni intervall enam ei kehti. Kui elementi ei oleks kogu loendist leitud, oleks tagastatud -1.

? Koodi ülevaade

Nüüd, kui teil on visuaalne intuitsioon algoritmi kulisside taga toimimisest, sukeldume iteratiivsesse Pythoni rakendusse, analüüsides seda rea ​​kaupa:

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

Päis

Siin on funktsiooni päis:

def binary_search(data, elem):

Selleks on vaja kahte argumenti:

  • Järjestatud elementide järjestus (näiteks: loend, dupleks või string).
  • Element, mida me tahame leida.

Esialgne intervall

Järgmine rida määrab esialgse alumise ja ülemise piiri:

low = 0 high = len(data) - 1

Esialgne alumine piir on indeks 0ja esialgne ülemine piir on jada viimane indeks.

Silmus

Kordame protsessi kehtiva intervalli olemasolul, samal ajal kui alumine piir on väiksem või võrdne ülemise piiriga.

while low <= high:

? Nõuanne: pidage meeles, et piirid on indeksid.

Keskmine element

Igal iteratsioonil peame leidma keskmise elemendi indeksi. Selleks lisame alumise ja ülemise piiri ning jagame tulemuse täisarvu jagamise abil 2-ga.

middle = (low + high)//2

? Nõuanne: me kasutame täisarvude jagamist juhul, kui loend või intervall sisaldab paarisarvu elemente. Näiteks, kui nimekiri oli 6 elemendid ja me ei kasutanud täisarv jagunemise, middleoleks tulemus (0 + 5)/2, mis on 2.5. Indeks ei saa olla ujuk, seega kärbime kümnendosa, kasutades //ja valides indeksi elemendi 2.

Võrdlused

Nende tingimustega (vt allpool) määrame, mida teha sõltuvalt keskmise elemendi väärtusest data[middle]. Võrdleme seda sihtelemendiga, mida otsime.

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

On kolm võimalust:

  • Kui keskmine element on võrdne otsitava elemendiga, tagastame indeksi kohe, kuna leidsime elemendi.
if data[middle] == elem: return middle
  • Kui keskmine element on suurem kui otsitav element, määrame ülemise piiri ümber, kuna teame, et sihtelement asub loendi alumises osas.
elif data[middle] > elem: high = middle - 1
  • Muul juhul on ainus võimalus, et keskmine element on väiksem kui otsitav element, seega määrame alumise piiri ümber, kuna teame, et sihtelement on loendi ülemises pooles.
else: low = middle + 1

Elementi ei leitud

Kui tsükkel on lõpetatud ilma elementi leidmata, tagastatakse väärtus -1.

return -1

ja binaarotsingu algoritm on lõplikult juurutatud:

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

? Erijuhtumid

Need on mõned konkreetsed juhtumid, mis võivad teile selle algoritmiga tööle asudes leida:

Korduvad elemendid

Kui otsitavat elementi järjestuses korratakse, sõltub tagastatav indeks elementide arvust ja toimingute järjestusest, mille algoritm järjestusega täidab.

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

Elementi ei leitud

Kui elementi ei leitud, tagastatakse -1.

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

Tühi järjestus

Kui jada on tühi, tagastatakse -1.

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

Sorteerimata järjestus

Kui jada on sortimata, pole vastus õige. Õige indeksi saamine on puhas kokkusattumus ja see võib tuleneda elementide järjestusest järjestuses ja algoritmi teostatavate toimingute järjestusest.

See näide tagastab õige tulemuse:

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

Kuid see ei:

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

? Nõuanne: mõelge, miks esimene näide annab õige tulemuse. Vihje: See on puhas juhus, et elementide järjekord paneb algoritmi jõudma õige indeksini, kuid sammhaaval protsess hindab 0siis 2ja lõpuks 6. Sel konkreetsel juhul leitakse selle konkreetse elemendi jaoks õige indeks isegi siis, kui järjestust pole sorteeritud.

? Keerulisem näide

Nüüd, kui olete algoritmi ja selle Pythoni juurutamisega paremini kursis, on siin üks keerulisem näide:

Selles loendis soovime binaarotsingu abil leida elemendi 45 indeksi :

Esimene kordus

Valitakse alumine ja ülemine piir:

Keskmine element ( 26 ) on valitud:

Kuid keskmine element ( 26 ) pole see element, mida me otsime, see on väiksem kui 45 :

Teine kordus

Seega võime kõik elemendid, mis on väiksemad kui keskmine element, kõrvale heita ja uued piirid valida. Uus alumine piir ( 27 ) on element, mis asub vahetult eelmisest keskmisest elemendist paremal:

? Nõuanne: pidage meeles, et loend on juba sorditud.

Valitud on uus keskmine element ( 30 ):

Keskmine element ( 30 ) pole otsitav element, see on väiksem kui 45 :

Kolmas kordus

Võime visata ära elemendid, mis on väiksemad või võrdsed 30-ga ja mida pole juba kõrvale visatud. Alumine piir on ajakohastatud 32-ni :

Siin on meil huvitav juhtum: keskmine element on praeguse intervalli üks piiridest, sest see (7+8)//2on 7.

Keskmine element ( 32 ) ei ole see element, mida me otsime ( 45 ), see on väiksem.

Neljas kordus

Võime visata 32- st väiksemad või võrdsed elemendid, mida pole juba kõrvale visatud.

Siin on meil veel üks väga huvitav juhtum: intervallil on ainult üks element.

? Nõuanne: see intervall on kehtiv, kuna kirjutasime selle tingimuse while high <= low:, mis sisaldab intervalle, kus alumise piiri indeks on võrdne ülemise piiri indeksiga.

Keskmine element on intervalli ainus element, kuna (8+8)//2on 8, nii et keskmise elemendi indeks on 8 ja keskmine element 45 .

Nüüd on keskmine element see element, mida otsime, 45 :

Seega tagastatakse väärtus 8 (indeks):

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

? lisapraktika

Kui soovite selle algoritmiga veidi harjutada, proovige selgitada, kuidas algoritm kulisside taga töötab, kui seda sellesse loendisse rakendatakse, et leida täisarv 90 :

[5, 8, 15, 26, 38, 56]
  • Mis toimub samm-sammult?
  • Mis väärtus tagastatakse?
  • Kas element on leitud?

Loodan väga, et teile meeldis minu artikkel ja see oli teile kasulik. Nüüd saate Pythonis rakendada kahendotsingu algoritmi. Vaadake minu veebikursust "Pythoni algoritmide otsimine ja sorteerimine: praktiline lähenemine". Jälgi mind Twitteris. ⭐️