13-Vyhledavani
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
Ukázka činnosti algoritmu binárního
vyhledávání
• Uvažujme posloupnost 2, 4, 5, 8, 9. Máme najít prvek s hodnotou 4.
• 1. krok 𝑎𝑠 = 5, 𝑥 = 4
2, 4, 5, 8, 9
4 < 5 (dále hledáme už jen v části A)
2, 4
• 2. krok 𝑎𝑠 = 2, 𝑥 = 4
2, 4
4 < 2 4 >2 (dále hledáme už jen v části B)
Ukázka činnosti algoritmu binárního
vyhledávání
• 3. krok 𝑎𝑠 = 4, 𝑥 = 4
4 4 < 4 4 > 4 4 = 4 (prvek nalezen)
Příklad použití metody binárního vyhledávání
• Je dáno pole obsahující vzestupně setříděné prvky:
1 2 4 5 7 8 15 28 31 39 .
• Popište konkrétně jednotlivé kroky binárního vyhledávání pokud
hledáme:
a) Prvek s hodnotou 15
b) Prvek s hodnotou 3
Ukázka činnosti algoritmu binárního
vyhledávání
• Uvažujme posloupnost 2, 4, 5, 8, 9. Máme najít prvek s hodnotou 7.
• 1. krok 𝑎𝑠 = 5, 𝑥 = 7
2, 4, 5, 8, 9
7 < 5 7 > 5 (dále hledáme už jen v části B)
8, 9
• 2. krok 𝑎𝑠 = 8, 𝑥 = 7
8, 9
7 < 8 (Hledaný prvek by měl ležet nalevo od prvku 8, ale tam už
žádný prvek není. Hledání proto končí neúspěchem.)
Složitost metody binárního vyhledávání
• V prvním kroku prohledáváme pole délky 𝑛 prvků.
• Ve druhém kroku v případě lichého 𝑛 budeme prohledávat už jen
𝑛−1
2 ,
v případě sudého počtu prvků budeme prohledávat maximálně
𝑛
2
prvků.
• Dále budeme uvažovat horší případ
𝑛
2 prvků.
Složitost metody binárního vyhledávání
Krok
Délka prohledávané části