13-Vyhledavani

BPC-ALD 

13. přednáška 

Vyhledávání v lineární datové struktuře, Binární vyhledávání v poli, 

složitost algoritmu. Binární vyhledávací stromy, určení složitost 

algoritmu. 

rev. 2019.8 

Ing. T. Macho, Ph.D. (macho@feec.vutbr.cz) 

Vyhledávání 

Definice vyhledávání 

• Je dána množina 𝑛 prvků 𝑎1, 𝑎2, … , 𝑎𝑛. 
• Dále je zadána hodnota prvku, označme ji 𝑥. 

• V případě hledání mezi strukturovanými prvky je zadána hodnota klíče. 

• Cílem je nalézt v množině prvků 𝑎1, 𝑎2, … , 𝑎𝑛 prvek, pro který platí 

𝑥 = 𝑎𝑖. 

Vyhledávání v lineární datové struktuře 

Vyhledávání v lineární datové struktuře 

• Množina prvků v níž provádíme vyhledávání je tvořena lineární 

datovou strukturou - polem, vázaným seznamem. 

• Předpokládáme, že prvky jsou v lineární datové struktuře uloženy 

nesetříděné. 

• Musíme postupně procházet prvky (např. směrem od začátku ke 

konci) a každý prvek srovnat s hledanou hodnotou 𝑥. 

Počet srovnání při vyhledávání v lineární 
datové struktuře 
• Minimální: 1 (hledaný prvek je na první pozici) 
• Maximální: 𝑛 (hledaný prvek je na poslední pozici) 
• Průměrný: 

𝑛+1

2  

Příklad implementace lineárního vyhledávání 
v poli 
size_t i = 0; 
for(; i < n; ++i) 
     if(a[i] == x) break; 
 
if(i < n)  
     {// prvek byl nalezen} 
else      {// prvek nebyl nalezen}