BPC-ALD_Zpracované_otazky_ke_zkousce

Podmínkou je setříděné pole. Nalezneme prvek as, který je uprostřed dané oblasti (v prvním kroku je uprostřed 

celého pole). Index prvku 

as získáme např. celočíselným dělením dvěma součtu indexů dvou prvků, ohraničujících 

konkrétní oblast. tzn. [ index prvku 

as = (index 1.-ho prvku oblasti + index posledníhoho prvku oblasti) / 2]. Ve 

výsledku má-

li oblast lichý počet prvků, je to přesně ten uprostřed a má-li oblast sudý počet prvků, je to ten levý z 

dvojice uprostřed oblasti (nicméně vyberete-li ten pravý, výsledek bude stejný). Potom provedeme porovnání 
hledaného prvku X s prvkem 

as. Je-li X < as, musí se hledaný prvek nacházet v oblasti A (nalevo od prvku as ). V 

opačném případě se prvek nachází napravo od as - v oblasti B). Obsahuje-li oblast, ve které hledáme, alespoň jeden 
prvek, můžeme rekurzivně použít celý dosavadní postup. Pokud neplatí X < as ani X > as, zkusíme zda X == as. 
Pakliže toto porovnání platí, hledaným prvkem je prvek as, pokud neplatí, hledaný prvek se v poli nenachází - v obou 
případech vyhledávání končí. 

Časová složitost této metody je O(log2(n)). 

A) Hledáme prvek 15:  (1, 2, 4, 5, 7, 8, 15, 28, 31, 39) -> s 

= (0+9)/2 = 4 (ve středu je prvek as s indexem 4 a ten má 

hodnotu 7) -

> 15>7 takže dále budeme hledat v oblasti B (8, 15, 28, 31, 39) -> s = (5+9)/2 = 7 (as = 28) -> 15<28 

takže dále budeme hledat v oblasti A’ (8, 15) (což je levá podoblast oblasti B) -> s = (5+6)/2 = 5 (as = 8) -> 15>8 takže 
dále budeme hledat v oblasti B’ (15) (což je pravá podoblast podoblasti A’) -> s = (6+6)/2 = 6 (as = 8) -> 15==15 -> 
našli jsme hledaný prvek. 

B) Hledáme prvek 38:  (1, 2, 4, 5, 7, 8, 15, 28, 31, 39) -> s = (0+9)/2 = 4 (

as = 7) -> 38>7 takže dále budeme hledat v