Bisekcija/Implementacija Java

Iz MaFiRaWiki

Metoda vrne -1, če ne najde podatka.

Rešitev z zanko

  1. public static int bisekcija(int[] a, int x){
  2. int i = 0;
  3. int j = a.length;
  4. while (i <= j) {
  5. int k = (i + j) / 2;
  6. if (a[k] == x) { return k; }
  7. else if (a[k] < x) { i = k + 1; }
  8. else { j = k - 1; }
  9. }
  10. return -1;
  11. }

Rešitev z rekurzivno funkcijo

  1. public static int bisekcija(String[] a, String x) {
  2. return bisekcija(a, x, 0, a.length - 1);
  3. }
  4.  
  5. public static int bisekcija(String[] a, String x, int i, int j) {
  6. if (i > j) { return -1; }
  7. else {
  8. int k = (i+j)/2;
  9. int c = a[k].compareTo(x);
  10. if (c < 0) { bisekcija(a, x, k+1, j); }
  11. else if (c > 0) { bisekcija(a, x, i, k-1); }
  12. else { return k; }
  13. }
  14. }
Osebna orodja