21. 2. 2023
Na kterém indexu v poli se nachází daný klíč k?
array-search
<-- ar:[]key — prohledávané pole
<-- k:key — hledaný klíč
--> int — index klíče k nebo -1, pokud v ar není
pro index i od 0 do len(arr)
pokud ar[i] == k vrať i
vrať -1
Složitost v nejhorším případě je Θ(n), kde n je velikost pole. Pokud budeme ovšem vyhledávat v poli, které je střízené, tak složitost v nejhoším případě bude lineární.
Mohli bychom se také zaměřit na složitost v průměrném případě, kde bychom se potřebovali znát frekvenci vyhledávání klíčů.
Předpokladem je setřízené pole, ve kterém vyhledáváme. Podrobný postup byl ukázán na cvičení. Základní princip je, že postupně si rozdělujeme pole, ve které části vyhledáváme. Složitost algoritmu v nejhorším případě je Θ(log n).