| 9 | |
| 10 | /* Returns index of x if present, else returns -1 */ |
| 11 | public static int fibMonaccianSearch(int arr[], int x, |
| 12 | int n) |
| 13 | { |
| 14 | /* Initialize fibonacci numbers */ |
| 15 | int fibMMm2 = 0; |
| 16 | int fibMMm1 = 1; |
| 17 | int fibM = fibMMm2 + fibMMm1; |
| 18 | |
| 19 | while (fibM < n) { |
| 20 | fibMMm2 = fibMMm1; |
| 21 | fibMMm1 = fibM; |
| 22 | fibM = fibMMm2 + fibMMm1; |
| 23 | } |
| 24 | |
| 25 | int offset = -1; |
| 26 | |
| 27 | while (fibM > 1) { |
| 28 | int i = min(offset + fibMMm2, n - 1); |
| 29 | |
| 30 | if (arr[i] < x) { |
| 31 | fibM = fibMMm1; |
| 32 | fibMMm1 = fibMMm2; |
| 33 | fibMMm2 = fibM - fibMMm1; |
| 34 | offset = i; |
| 35 | } |
| 36 | |
| 37 | else if (arr[i] > x) { |
| 38 | fibM = fibMMm2; |
| 39 | fibMMm1 = fibMMm1 - fibMMm2; |
| 40 | fibMMm2 = fibM - fibMMm1; |
| 41 | } |
| 42 | |
| 43 | else |
| 44 | return i; |
| 45 | } |
| 46 | |
| 47 | if (fibMMm1 == 1 && arr[n-1] == x) |
| 48 | return n-1; |
| 49 | |
| 50 | return -1; |
| 51 | } |
| 52 | |
| 53 | public static void main(String[] args) |
| 54 | { |