13-Vyhledavani
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 po ukončení cyklu bude i < n, byl prvek nalezen.
• Je-li i = n, prvek nalezen nebyl.
Příklad implementace lineárního vyhledávání
v poli s použitím zarážky
a[n] = x;
size_t i = 0;
for(;; ++i)
if(a[i] == x) break;
if(i < n)
{// prvek byl nalezen}
else {// prvek nebyl nalezen}
Binární vyhledávání v poli
Binární vyhledávání v poli
• Vyhledávání v poli je mnohem efektivnější, jsou-li prvky pole
setříděné podle velikosti: 𝑎1 ≤ 𝑎2 ≤ ⋯ ≤ 𝑎𝑛.
• Potom pro vyhledávání můžeme použít algoritmus binárního
vyhledávání, často nazývaný vyhledávání půlením intervalu (bisekce).
Popis algoritmu binárního vyhledávání
• Vezmeme prvek, který je v poli uprostřed
• Při sudém počtu prvků jsou uprostřed dva prvky, vezmeme např. levý prvek.
A
B
𝑎𝑖 < 𝑎𝑠
𝑎𝑖 > 𝑎𝑠
𝑎𝑠
Prvek uprostřed
Popis algoritmu binárního vyhledávání
• Provedeme srovnání hledané hodnoty 𝑥 s hodnotou středního prvku
𝑎𝑠.
• Je-li 𝑥 < 𝑎𝑠, (pokud hledaný prvek v poli vůbec je), musí být v části A.
Obsahuje-li část A alespoň jeden prvek, rekurzivně na ni provedeme
stejný postup. Neobsahuje-li část A už žádný prvek, vyhledávání
neúspěšně končí.
• Je-li 𝑥 > 𝑎𝑠, (pokud hledaný prvek v poli vůbec je), musí být v části B.
Obsahuje-li část B alespoň jeden prvek, rekurzivně na ni provedeme
stejný postup. Neobsahuje-li část B už žádný prvek, vyhledávání
neúspěšně končí.
Popis algoritmu binárního vyhledávání
• Pokud neplatí 𝑥 < 𝑎𝑠 ani 𝑥 > 𝑎𝑠, musí platit 𝑥 = 𝑎𝑠, čímž
vyhledávání končí, protože 𝑎𝑠 je hledaným prvkem (a
nepředpokládáme, že je v poli více prvků se stejnou hodnotu 𝑥).