Bisekcija/Implementacija CPP

Iz MaFiRaWiki

Uporaba

  1. bisekcija(polje, dolzina_polja, iskano_stevilo);
  2. /*
  3. Dolžina polja je n-1.
  4. Če iskanega števila ni vrne -1, drugače njegov index.
  5. */

Rešitev z zanko

  1. /* Gregor Janezic, FERI */
  2.  
  3. int bisekcija(int polje[], int dolzina, int iskano) {
  4. int i = 0, j = 0;
  5. while(i <= dolzina) {
  6. j = (i + dolzina) / 2;
  7. if(polje[j] < iskano)
  8. i = j + 1;
  9. else
  10. if(polje[j] > iskano)
  11. dolzina = j - 1;
  12. else
  13. return j;
  14. }
  15. return -1;
  16. }

Rešitev z rekurzivno funkcijo

  1. /* Gregor Janezic, FERI */
  2.  
  3. int bisekcija(int polje[], int dolzina, int iskano, int i=0) {
  4. if(i <= dolzina) {
  5. int j = (i + dolzina) / 2;
  6. if(polje[j] < iskano)
  7. return bisekcija(polje, dolzina, iskano, j+1);
  8. else
  9. if(polje[j] > iskano)
  10. return bisekcija(polje, j-1, iskano, i);
  11. else
  12. return j;
  13. } else
  14. return -1;
  15. }
Osebna orodja