Cvičení 2 - lineární datové struktury I

Témata

• pole,
• vyhledávání v poli (sekvenční, binární, interpolační).

Úkoly

1. Implementujte funkci int sequence_search(int array[], int element) pro sekvenční vyhledávání v poli vracející index, na kterém se prvek nachází, nebo -1 pokud se tam nenachází.
2. Implementujte funkci int binary_search(int array[], int element) pro binární vyhledávání v setřízeném poli vracející index, na kterém se prvek nachází, nebo -1 pokud se tam nenachází.
3. Implementujte funkci int interpolation_search(int array[], int element) pro interpolační vyhledávání v setřízeném poli vracející index, na kterém se prvek nachází, nebo -1 pokud se tam nenachází.
4. (*) Porovnejte tyto funkce pro různá pole a hledané hodnoty. Zaměřte se zejména na skutečný počet provedených porovnání. Zkuste najít příklady polí a hledaných hodnot, které pro jednotlivé algoritmy budou představovat nejhorší a nejlepší případy.

Úkoly označené (*) nejsou povinné (nemusíte je odevzdávat).