Cvičení 2 - pole

Témata

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

Ú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í.
3. Implementujte funkci int interpolation_search(int array[], int size, 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 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í.
3. Implementujte funkci interpolation_search(array: list[int], element: int) -> int 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.