DICHOTOMICKÉ VYHLEDÁVÁNÍ

PROBLÉM
Je dáno vzestupně uspořádané pole A.1,...,A.N a hledaná hodnota V. Vyhledávací funkce vrací index V, jestliže se V nachází v poli A., jinak vrací N+1.

ALGORITMUS
Rozdělíme pole na dvě části; určíme ve které z nich musí hledaný prvek být; tuto část opět rozdělíme na dvě části ... (algoritmus se také nazývá vyhledávání půlením intervalu). V průměru je potřeba lgN porovnání.

IMPLEMENTACE
Jednotka: vnitřní funkce
 
Globální proměnné: uspořádané pole A.1,...,A.N libovolných prvků
 
Parametry: přirozené číslo N, libovolná hodnota V
 
Vrací: index prvku V v poli A. nebo číslo N+1, když V není prvkem pole.

 

BINARY_SEARCH: procedure expose A.
parse arg N, V
L = 1; R = N
do while L <= R
  M = (L + R) % 2
  if V = A.M then leave
  if V < A.M then R = M - 1; else L = M + 1
end
if A.M = V then return M; else return N + 1

 

SOUVISLOSTI


Obálka Obsah Index Hlavní stránka

změněno 30. července 2000
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.