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


Creative Commons License Sbírka úloh z jazyka C. © Katedra informatiky Univerzity Palackého v Olomouci, 2009.
Projekt byl vytvořen za podpory grantu FRVŠ 2061/2009/G1.