Dvejetainė paieška „Python“: vizualus įvadas

Sveiki

Šiame straipsnyje sužinosite, kaip „Dvejetainės paieškos“ algoritmas veikia užkulisiuose ir kaip galite jį įgyvendinti „Python“.

Visų pirma sužinosite:

  • Kaip algoritmas veikia užkulisiuose, norėdamas rasti tikslinį elementą.
  • Kaip jo „Python“ diegimas veikia eilutėmis.
  • Kodėl tai yra labai efektyvus algoritmas, palyginti su tiesine paieška.
  • Jos pranašumai ir reikalavimai.

Pradėkime! ✨

? Įvadas į dvejetainę paiešką

Šis algoritmas naudojamas surasti elementą eilės tvarka (pavyzdžiui: sąrašas, paketas ar eilutė).

Reikalavimai

Norint taikyti dvejetainės paieškos algoritmą sekai, seka jau turi būti rūšiuojama didėjimo tvarka. Priešingu atveju algoritmas neras teisingo atsakymo. Jei taip, tai bus visiškai atsitiktinumas.

? Patarimas: Prieš pritaikydami dvejetainę paiešką, galite rūšiuoti seką naudodami rūšiavimo algoritmą, kuris atitinka jūsų poreikius.

Įvestis ir išvestis

Algoritmui (įgyvendintam kaip funkcija) reikalingi šie duomenys:

  • Sutvarkyta elementų seka (pavyzdžiui: sąrašas, paketas, eilutė).
  • Tikslinis elementas, kurio ieškome.

Jis grąžina ieškomo elemento indeksą , jei jis randamas. Jei elementas nerastas, grąžinama -1.

Efektyvumas

Tai yra labai efektyvu, palyginti su linijine paieška (ieškant elemento po vieną, pradedant nuo pirmo), nes kiekviename žingsnyje galime „išmesti“ pusę sąrašo.

Pradėkime nerti į šį algoritmą.

? Vaizdinis apžvalga

Šiam sąrašui pritaikysime dvejetainės paieškos algoritmą:

? Patarimas: atkreipkite dėmesį, kad sąrašas jau surūšiuotas. Joje buvo rodikliai kaip vizuali nuoroda.

Įvartis

Norime rasti sveikojo skaičiaus indeksą 67 .

Intervalas

Apsimeskime, kad mes esame algoritmas. Kaip pradėti procesą?

Pirmiausia mes pasirenkame dvi intervalo ribas, kuriose norime ieškoti. Norime ieškoti visame sąraše, todėl indeksą pasirenkame 0kaip apatinę, o indeksą - 5kaip viršutinę:

Vidurinis elementas

Dabar turime rasti vidurio elemento indeksą šiame intervale. Tai darome pridėdami apatinę ir viršutinę ribas ir padalydami rezultatą iš 2 naudodami sveikojo skaičiaus padalijimą.

Šiuo atveju (0 + 5)//2taip yra 2todėl, kad padalijimo rezultatas 5/2yra 2.5ir sveikasis skaičius sutrumpina dešimtainę dalį.

Taigi vidurinis elementas yra 2 rodyklėje , o vidurinis elementas yra skaičius 6 :

Palyginimai

Dabar turime pradėti lyginti vidurinį elementą su savo tiksliniu elementu, kad pamatytume, ką turime daryti toliau.

Mes klausiame:

Ar vidurinis elementas yra lygus elementui, kurio ieškome?

6 == 67 # False

Ne, taip nėra.

Taigi mes klausiame:

Ar vidurinis elementas yra didesnis už ieškomą elementą?

6 > 67 # False

Ne, taip nėra.

Taigi vidurinis elementas yra mažesnis už elementą, kurio ieškome.

6 < 67 # True

Išmeskite elementus

Kadangi sąrašas jau yra surūšiuotas, tai mums sako ką nors nepaprastai svarbaus. Tai mums sako, kad galime „išmesti“ apatinę sąrašo pusę, nes žinome, kad visi elementai, einantys prieš vidurinįjį elementą, bus mažesni už elementą, kurio ieškome, todėl mūsų tikslinio elemento nėra.

Pradėti iš naujo - pasirinkti ribas

Ką darysime toliau? Mes atsisakėme elementų ir ciklas vėl kartojamas.

Turime pasirinkti naujo intervalo ribas (žr. Toliau). Tačiau atkreipkite dėmesį, kad viršutinė riba lieka nepakitusi ir keičiama tik apatinė riba.

Taip yra todėl, kad ieškomas elementas gali būti viršutinėje sąrašo pusėje. Viršutinė riba lieka nepažeista, o apatinė riba pakeičiama, kad „susitrauktų“ intervalas iki intervalo, kuriame būtų galima rasti mūsų tikslinį elementą.

? Patarimas: Jei vidurinis elementas būtų didesnis už ieškomą elementą, viršutinė riba būtų pakeista, o apatinė - nepažeista. Tokiu būdu mes išmesime viršutinę sąrašo pusę ir toliau ieškosime apatinėje pusėje.

Vidurinis elementas

Dabar turime rasti vidurinio elemento indeksą, pridėdami apatinę ribą prie viršutinės ribos ir padalydami rezultatą iš 2 naudodami sveikojo skaičiaus padalijimą.

Rezultatas (3+5)//2yra 4, taigi vidurinis elementas yra rodyklėje,4 o vidurinis elementas yra 67 .

Palyginimai

Mes klausiame:

Ar vidurinis elementas yra lygus elementui, kurio ieškome?

67 == 67 # True

Taip tai yra! Taigi elementą radome 4 rodyklėje . Pateikiama 4 reikšmė ir algoritmas sėkmingai užbaigtas.

? Patarimas: Jei elementas nebūtų rastas, procesas būtų tęsiamas tol, kol intervalas nebegalioja. Jei elementas nebūtų rastas visame sąraše, būtų grąžinta -1.

? Kodo peržiūra

Dabar, kai turite vaizdinę intuiciją, kaip algoritmas veikia užkulisiuose, pasinerkime į iteracinį „Python“ diegimą, analizuodami jį eilutėje po eilutės:

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

Antraštė

Čia mes turime funkcijos antraštę:

def binary_search(data, elem):

Tam reikia dviejų argumentų:

  • Rikiuota elementų seka (pavyzdžiui: sąrašas, paketas ar eilutė).
  • Elementas, kurį norime rasti.

Pradinis intervalas

Kitoje eilutėje nustatomos pradinės apatinės ir viršutinės ribos:

low = 0 high = len(data) - 1

Pradinė apatinė riba yra indeksas, 0o pradinė viršutinė riba yra paskutinis sekos indeksas.

Kilpa

Mes pakartosime procesą, kol yra galiojantis intervalas, o apatinė riba yra mažesnė arba lygi viršutinei ribai.

while low <= high:

? Patarimas: atminkite, kad ribos yra indeksai.

Vidurinis elementas

Kiekvienoje iteracijoje turime rasti vidurinio elemento indeksą. Norėdami tai padaryti, pridedame apatinę ir viršutinę ribas ir padalijame rezultatą iš 2 naudodami sveikojo skaičiaus padalijimą.

middle = (low + high)//2

? Patarimas: Mes naudojame sveikųjų skaičių padalijimą, jei sąraše arba intervale yra lyginis elementų skaičius. Pavyzdžiui, jei sąraše turėjo 6 elementus, o mes nesinaudojo sveikasis skyriaus, middlebūtų rezultatas (0 + 5)/2, kuris yra 2.5. Indeksas negali būti plūduriuojantis, todėl sutrumpiname dešimtainę dalį naudodami //ir pasirinkdami indekso elementą 2.

Palyginimai

Su šiais sąlyginiais (žr. Toliau) mes nustatome, ką daryti, atsižvelgiant į vidurinio elemento vertę data[middle]. Palyginame jį su ieškomu elementu.

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

Yra trys variantai:

  • Jei vidurinis elementas yra lygus ieškomam elementui, mes nedelsdami grąžiname indeksą, nes radome elementą.
if data[middle] == elem: return middle
  • Jei vidurinis elementas yra didesnis nei ieškomas elementas, viršutinę ribą priskiriame iš naujo, nes žinome, kad tikslinis elementas yra apatinėje sąrašo pusėje.
elif data[middle] > elem: high = middle - 1
  • Kita vertus, liko tik tai, kad vidurinis elementas yra mažesnis nei ieškomas elementas, todėl mes priskyrėme apatinę ribą, nes žinome, kad tikslinis elementas yra viršutinėje sąrašo pusėje.
else: low = middle + 1

Elementas nerastas

Jei ciklas baigiamas neradus elemento, grąžinama vertė -1.

return -1

ir mes turime galutinį dvejetainės paieškos algoritmo įgyvendinimą:

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

? Ypatingos bylos

Tai yra keli konkretūs atvejai, kuriuos galite rasti pradėdami dirbti su šiuo algoritmu:

Pakartojami elementai

Jei ieškomas elementas bus pakartotas sekoje, grąžinamas indeksas priklausys nuo elementų skaičiaus ir nuo algoritmo atliktų sekų operacijų sekos.

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

Elementas nerastas

Jei elementas nerastas, grąžinama -1.

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

Tuščia seka

Jei seka tuščia, grąžinama -1.

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

Nerūšiuota seka

Jei seka nerūšiuota, atsakymas nebus teisingas. Teisingo indekso gavimas yra grynas sutapimas ir tai gali būti dėl elementų eilės eilės ir algoritmo atliktų operacijų sekos.

Šis pavyzdys pateikia teisingą rezultatą:

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

Bet šis:

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

? Patarimas: pagalvokite, kodėl pirmas pavyzdys pateikia teisingą rezultatą. Patarimas: Visiškas sutapimas, kad elementų tvarka atsitinka taip, kad algoritmas pasiektų teisingą indeksą, tačiau žingsnis po žingsnio vertinamas 0tada 2ir pagaliau 6. Šiuo konkrečiu atveju šiam konkrečiam elementui rodomas teisingas indeksas, net jei seka nėra rūšiuojama.

? Sudėtingesnis pavyzdys

Dabar, kai esate labiau susipažinęs su algoritmu ir jo „Python“ diegimu, pateikiame sudėtingesnį pavyzdį:

Norime rasti elemento 45 indeksą šiame sąraše naudodami dvejetainę paiešką:

Pirmoji kartojimas

Pasirenkama apatinė ir viršutinė ribos:

Pasirenkamas vidurinis elementas ( 26 ):

Bet vidurinis elementas ( 26 ) nėra tas elementas, kurio mes ieškome, jis yra mažesnis nei 45 :

Antroji kartojimas

Taigi mes galime išmesti visus elementus, kurie yra mažesni už vidurinį elementą, ir pasirinkti naujas ribas. Nauja apatinė riba ( 27 ) yra elementas, esantis iškart dešinėje nuo ankstesnio vidurinio elemento:

? Patarimas: atminkite, kad sąrašas jau surūšiuotas.

Pasirinktas naujas vidurinis elementas ( 30 ):

Vidutinis elementas ( 30 ) nėra tas elementas, kurio ieškome, jis yra mažesnis nei 45 :

Trečioji kartojimas

Mes galime išmesti mažesnius arba lygius 30 elementų , kurie dar nebuvo išmesti. Apatinė riba atnaujinama iki 32 :

Čia mes turime įdomų atvejį: vidurinis elementas yra viena iš dabartinio intervalo ribų, nes (7+8)//2yra 7.

Vidutinis elementas ( 32 ) nėra tas elementas, kurio ieškome ( 45 ), jis yra mažesnis.

Ketvirtoji kartojimas

Mes galime išmesti mažesnius arba lygius 32 elementus , kurie dar nebuvo išmesti.

Čia mes turime dar vieną labai įdomų atvejį: intervalas turi tik vieną elementą.

? Patarimas: Šis intervalas galioja, nes mes parašėme šią sąlygą while high <= low:, į kurią įeina intervalai, kai apatinės ribos indeksas yra lygus viršutinės ribos indeksui.

Vidutinis elementas yra vienintelis intervalo elementas, nes (8+8)//2yra 8, taigi vidurinio elemento indeksas yra 8, o vidurio elementas yra 45 .

Dabar vidurinis elementas yra elementas, kurio ieškome, 45 :

Taigi grąžinama vertė 8 (indeksas):

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

? Papildoma praktika

Jei norėtumėte papildomai praktikuoti šį algoritmą, pabandykite paaiškinti, kaip algoritmas veikia užkulisiuose, kai jis pritaikomas šiame sąraše, kad rastumėte sveikąjį skaičių 90 :

[5, 8, 15, 26, 38, 56]
  • Kas vyksta žingsnis po žingsnio?
  • Kokia vertė grąžinama?
  • Ar elementas rastas?

Labai tikiuosi, kad jums patiko mano straipsnis ir jis buvo naudingas. Dabar „Python“ galite įdiegti dvejetainės paieškos algoritmą. Peržiūrėkite mano internetinius kursus „Python paieškos ir rūšiavimo algoritmai: praktinis požiūris“. Sekite mane „Twitter“. ⭐️