BPC-ALD - Skripta_rev2019_2

i

a

x

=   . 

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

Studijní cíle:  Tato  část  vysvětluje  principy  vyhledávání  v  lineárních  datových  strukturách  a 
poskytuje jejich podrobný popis včetně základního nástinu, jak je implementovat. 

Klíčová slova: Vyhledávání, zarážka, binární vyhledávání. 

Potřebný čas: 1 hodina 30 minut 

Mezi nejjednodušší případy vyhledávání patří vyhledávání v lineární datové struktuře, tj. v poli 
nebo  v  seznamu.  Přepokládáme  přitom,  že  prvky  jsou  v ní  uloženy  v libovolném  pořadí 
(nesetříděné). Není zde jiný způsob, než prvky postupně procházet (třeba od začátku směrem ke 
konci) a každý srovnat s hledanou hodnotou. Počet srovnání se přitom pohybuje od 1, jestliže 
hledaný prvek je hned první, po n, jestliže hledaný prvek je až poslední anebo hledaný prvek 
mezi prohledávanými prvky není obsažen (nebyl nalezen). Tedy 

Průměrný počet srovnání (je-li prvek nalezen) 

2

1

+

=

n

Maximální počet srovnání 

n

=  

Jde-li o vyhledávání v poli, je kód programu v tomto případě tak jednoduchý, že si ho můžeme 
uvést  (v  jazyce  C++,  C#).  Hledaná  hodnota  nechť  je  v proměnné  x  a  jako  index  použijeme 
proměnnou i. Předpokládáme, že index prvního prvku pole je 0. 

  i = 0; 

  for (;i<n;i++) if (x==a[i]]) break; 

  if (i<n) { /* prvek byl nalezen*/ } 

Je zřejmé, že v cyklu se kromě srovnání, zda prvek je roven hledané hodnotě, rovněž vždy dělá 
srovnání, zda už nejsme na konci pole (podmínka i<n). To lze odstranit a vyhledávání urychlit 
tak,  že  pole  s prvky  vytvoříme  o  jeden  prvek  větší  a  jako  poslední  prvek  v poli  před  každým 
prohledáváním dáme hledanou hodnotu (užívá se pro ni označení zarážka). Pak cyklus hledání 
vždy nalezne hledaný prvek a bude jen zapotřebí zjistit, zda tento prvek byl nalezen ještě před 
zarážkou.