BPC-ALD - Skripta_rev2019_2
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.
Pokud není x > as, zbývá už jen možnost, že platí x = as, čímž vyhledávání končí, neboť prvek as
je hledaným prvkem.
Příklad. Nechť v poli jsou prvky
1 3 5 8 12 15 21 24 32 40
A máme najít prvek x=15.
Střední prvek je číslo 12:
1 3 5 8 | 12 | 15 21 24 32 40
A protože hledaná hodnota je větší, pro další krok vezmeme část napravo
15 21 24 32 40
Střední prvek je číslo 24:
15 21 | 24 | 32 40
A protože hledaná hodnota je menší, vezmeme část nalevo
15 21
Střední prvek je nyní číslo 15:
Pro vyhledávání
v poli je výhodné,
když je setříděné.
− 61 −
- | 15 | 21
A střední prvek je zde roven hodnotě v proměnné x, čímž je i hledaným prvkem.
Složitost metody Při odvození složitosti vyjdeme z délky prohledávané části pole. V prvním kroku začínáme
celým polem, tedy n prvky. Pokud v něm hledaný prvek nebyl nalezen, pak do dalšího kroku
vezmeme část nalevo od něho nebo napravo od něho. Délka částí je
2
1
−
n
nebo
2
n
podle toho,
zda počet prvků n je lichý nebo sudý. Pro odvození vezmeme ten „horší“ případ, že délka části
vybrané pro následující krok je
2
n
.
Krok
Délka prohledávané části
1.
n
2.
2
n
3.
2
2
n
4.
3
2
n
….
k-tý
1
2 −
k
n
Zřejmě vyhledávání skončí nejpozději v kroku, kdy délka prohledávané části je už tvořena jen
jedním prvkem. Tedy položme
1
2
1
−
=
k
n
.
Úpravou
n
k
=
−1
2
.
A použitím funkce logaritmu
1
)
(
log
2
+
=
n
k
.
Maximální počet kroků logaritmicky závisí na počtu prvků v prohledávané posloupnosti.
V každém kroku provádíme nejvýše dvě operace srovnání. První operací zjistíme, zda hledaný
prvek je menší než střední prvek. Pokud ano, pokračujeme v hledání v části nalevo. Pokud ne,
druhou operací srovnání zjistíme, zda hledaný je větší než střední prvek, čímž rozhodneme, zda
pokračovat v hledání v části napravo anebo už jsme hledaný prvek našli.