IB111 – cv. 6
Binární vyhledávání
Miroslav Kadlec
Obsah
● Prezence
● https://www.fi.muni.cz/IB111/sbirka/06-
binarni_vyhledavani.html
● Binární vyhledávání
●
Hádání čísla člověkem
● Hádání čísla počítačem
● Ukázka půlení intervalů
● Aproximace kořenu funkce
● Vyhledávání v seřazeném seznamu
● Domácí úloha
Binární vyhledávání
● Hádání čísla člověkem
● Ukázka:
https://www.khanacademy.org/computer-programming/g
uess-my-number-2/6095780544249856
● Mám uhodnout číslo z daného intervalu, které si někdo
(počítač) myslí
● Mohu pokládat pouze otázku typu: "Je hledané číslo větší
nebo menší (případně stejné) než číslo XY?"
– Po každé takové otázce se mi zmenší počet možných hodnot
hledaného čísla
– V případě trefy jsme přímo informovaní o úspěchu a program
končí
● Jak se ptát co nejlépe (resp. Jak volit XY), aby se mi
počet možností co nejvíce zmenšil?
Binární vyhledávání
● Je vhodné se ptát na XY v polovině intervalu
● Podle odpovědi pak do další iterace vezmeme jako nový interval
horní nebo dolní polovinu původního
● Takovéto jednoznačné (deterministické) chování (výběr XY a
zmenšení uintervalu) můžeme zapsat algoritmicky s pomocí
Pythonu
● Hádání čísla počítačem
● Jsme na celých číslech
– Najde tento postup vždy hledané číslo?
● Stačí tedy jako ukonč. podmínka trefa do hledaného čísla?
– Když zjistím, že hledané číslo je větší, jaké přesně číslo mám zvolit za
novou dolní hranici, abych nic nepřeskočil ani nebral 2x?
● Nezapomeňme implementovat možnost trefy – úspěch a
ukončení
Metoda půlení intervalů
● Problém: Máme matematickou funkci (zapsanou
"function(x)"), která je na daném intervalu prostá a
má na něm kořen. Zkusíme ho aproximovat.
● Aplikace myšlenky binárního vyhledávání
● Neptáme se už přímo na XY ale na "function(XY)"
● Už jsme na reálných číslech
– Můžeme si dovolit zase brát za novou hranici číslo o 1 větší
(menší) než XY?
– Stačí jako ukončovací podmínka přesná trefa do hledaného čísla?
● Jak s pomocí kladnosti/zápornosti "function(x)" v dolní
hranici, uprostřed a v horní hranici zjistím, v které půlce
intervalu je kořen?
Vyhledávání v seřazeném seznamu
● Máme zjistit, jestli se v daném seřazeném
seznamu vyskytuje zadaný prvek (rozšíření –
návrat jeho pozice)
● Čím je reprezentována dolní/horní hranice?
– Indexem v seznamu, resp. prvním a posldním indexem
podseznamu, ve kterém se ještě hledaný prvek může
nacházet
● Kdy máme jistotu, že jsme prošli celý seznam?
– Až se potká dolní hranice s horní
Vyhledávání v seřazeném seznamu
● Máme zjistit, jestli se v daném seřazeném
seznamu vyskytuje zadaný prvek (rozšíření –
návrat jeho pozice)
● Čím je reprezentována dolní/horní hranice?
– Indexem v seznamu, resp. prvním a posldním indexem
podseznamu, ve kterém se ještě hledaný prvek může
nacházet
● Kdy máme jistotu, že jsme prošli celý seznam?
– Až se potká dolní hranice s horní
Domácí úloha 3
● Systém
https://www.hackerrank.com/domains?h_r=logo
● Vyberte si 15 příkaldů z části "Python" mimo
podčást "Introduction"
● Každý příklad je za 1 bod
● Správná řešení se vám logují – na dalším cviku
pak ukážete výpis z logu na vašem účtu