Hledání půlením intervalu
Téma: Rekurzivní funkce
Procvičované učivo: rekurze, funkce, pole, větvení
Napište v jazyku C rekurzivní funkci int puleni(int cisla[], int a, int b, int hledane)
, která pomocí metody půlení intervalu najde v zadaném setříděném poli cisla
hodnotu hledane
a vrátí její index v tomto poli. Připomínáme, že metoda půlení intervalu je založena na porovnání hodnoty hledaného čísla s číslem "uprostřed" právě prohledávaného intervalu (v našem případě intervalu mezi prvky s indexy a
a b
). Pokud se hodnoty rovnají, našli jsme hledané číslo a můžeme tedy přímo vrátit jeho index. Pokud se nerovnají, stačí (rekurzivním voláním) prohledávat pouze jeden z intervalů prvek s indexem a
až "prostřední prvek" nebo "prostřední prvek" až prvek s indexem b
.
Příklad použití:
int main(){ int p[11]; int i; for (i=0; i<11; i++) p[i] = 2*i+3; for (i=0; i<11; i++) printf("Cislo %i je na indexu: %i\n", 2*i+3, puleni(p,0,10, 2*i+3)); return 0; }
Příklad výstupu:
Cislo 3 je na indexu: 0 Cislo 5 je na indexu: 1 Cislo 7 je na indexu: 2 Cislo 9 je na indexu: 3 Cislo 11 je na indexu: 4 Cislo 13 je na indexu: 5 Cislo 15 je na indexu: 6 Cislo 17 je na indexu: 7 Cislo 19 je na indexu: 8 Cislo 21 je na indexu: 9 Cislo 23 je na indexu: 10
Povolené knihovny: stdio.h, stdlib.h