Cvičení 2 - pole

Témata

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

Úkoly C

1. Implementujte funkci int sequence_search(int array[], int size, 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 size, 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í.
   • Implementujte iterativní i rekurzivní verzi takové funkce.
3. Navrhněte a implementujte malý testovací systém, který implementované funkce porovná. 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. Zkuste porovnat i časy běhů na velkých polích.

Úkoly Python

1. Implementujte funkci sequence_search(array: list[int], element: int) -> int 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 binary_search(array: list[int], element: int) -> int 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í.
   • Implementujte iterativní i rekurzivní verzi takové funkce.
3. Navrhněte a implementujte malý testovací systém, který implementované funkce porovná. 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. Zkuste porovnat i časy běhů na velkých polích.