BPC-ALD - Skripta_rev2019_2

  a[n] = x; 

  i = 0; 

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

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

Potřeba najít 
nějaký údaj nebo 
hodnotu je v praxi 
dost častá. 

Hledání v poli je 
sice velmi 
jednoduché, 
nicméně málo 
efektivní. 

:

:

++i

++i

− 60 − 

4.2  Binární vyhledávání v poli 

V případě  pole  je  mnohem  příznivější  případ  pro  vyhledávání,  když  prvky  jsou  v  něm 
uspořádány (seřazeny) dle velikosti. Tj. platí pro ně 

n

n

a

a

a

a

≤

≤

≤

≤

−1

2

1

...

Zde se dá použít algoritmus binárního vyhledávání, často také nazývaný vyhledávání půlením 
intervalu. 

Popis algoritmu 

Vezmeme prvek, který je v poli uprostřed (je-li počet prvků sudý, jsou uprostřed dva prvky, zde 
vezmeme jeden z nich - při implementaci metody to zpravidla vychází tak, že se bere ten první), 
označme jeho index s. 

Následně provedeme srovnání hledané x hodnoty s hodnotou středního prvku as: 
Nejprve srovnáme, zda je x < as: 
Pokud ano, pak zřejmě hledaný prvek, pokud v poli vůbec je, musí být v části A, jež je nalevo 
od  středního  prvku  as.  Je-li  část  A  neprázdná  (obsahuje  aspoň  jeden  prvek),  rekurzivně  na  ni 

provedeme stejný postup. Je-li už  prázdná,  vyhledávání  neúspěšně  končí. Hledaný prvek není 
v poli obsažen. 

Pokud neplatí x < as , provedeme další srovnání. Srovnáme, zda je x > as: 
Pokud  ano, musíme  v  dalším  kroku  hledání  pokračovat v části  B,  jež  je  napravo  od  středního 
prvku  as.  Je-li  část  B  neprázdná  (obsahuje  aspoň  jeden  prvek),  rekurzivně  na  ni  provedeme 

stejný postup. Je-li už prázdná vyhledávání neúspěšně končí.