|
| 1 | +packagesrc.main.java.com.search; |
| 2 | + |
| 3 | +importstaticjava.lang.Math.min; |
| 4 | + |
| 5 | +/** |
| 6 | + * Fibonacci search is a method of searching a sorted array using a divide and conquer algorithm that narrows down |
| 7 | + * possible locations with the aid of Fibonacci numbers. Compared to binary search where the sorted array is divided |
| 8 | + * into two equal-sized parts, one of which is examined further, Fibonacci search divides the array into two parts that |
| 9 | + * have sizes that are consecutive Fibonacci numbers. |
| 10 | + * <p> |
| 11 | + * Worst-case performanceO(Log n) |
| 12 | + * Best-case performanceO(1) |
| 13 | + * Average performanceO(Log n) |
| 14 | + * Average space complexityO(1) |
| 15 | + */ |
| 16 | +publicclassFibonacciSearch { |
| 17 | +/** |
| 18 | + * @param array is an array where the element should be found |
| 19 | + * @param key is an element which should be found |
| 20 | + * @param <T> is any comparable type |
| 21 | + * @return The index position of the key in the array, returns -1 for empty array |
| 22 | + */ |
| 23 | +public <TextendsComparable<T>>intfindIndex(T[]array,Tkey) { |
| 24 | +intsize =array.length; |
| 25 | + |
| 26 | +if (size ==0) |
| 27 | +return -1; |
| 28 | + |
| 29 | +// Initialize the fibonacci numbers |
| 30 | +intfibN1 =1;// (n-1)th Fibonacci term |
| 31 | +intfibN2 =0;// (n-2)th Fibonacci term |
| 32 | +intfibN =fibN1 +fibN2;// nth Fibonacci term |
| 33 | + |
| 34 | +//fibN should store the smallest Fibonacci Number greater than or equal to size |
| 35 | +while (fibN <size) { |
| 36 | +fibN2 =fibN1; |
| 37 | +fibN1 =fibN; |
| 38 | +fibN =fibN2 +fibN1; |
| 39 | + } |
| 40 | + |
| 41 | +// Marks the eliminated range from front |
| 42 | +intoffset = -1; |
| 43 | + |
| 44 | +while (fibN >1) { |
| 45 | +// Check if fibN2 is a valid location |
| 46 | +inti =min(offset +fibN2,size -1); |
| 47 | + |
| 48 | +//If key is greater than the value at index fibN2, cuts the sub-array from offset to i |
| 49 | +if (array[i].compareTo(key) <0) { |
| 50 | +fibN =fibN1; |
| 51 | +fibN1 =fibN2; |
| 52 | +fibN2 =fibN -fibN1; |
| 53 | +offset =i; |
| 54 | + } |
| 55 | + |
| 56 | +//If x is greater than the value at index fibN2, cuts the sub-array after i+1 |
| 57 | +elseif (array[i].compareTo(key) >0) { |
| 58 | +fibN =fibN2; |
| 59 | +fibN1 =fibN1 -fibN2; |
| 60 | +fibN2 =fibN -fibN1; |
| 61 | + }elsereturni;//Element found |
| 62 | + } |
| 63 | +// comparing the last element with key |
| 64 | +if (fibN1 ==1 &&array[offset +1].compareTo(key) ==0) |
| 65 | +returnoffset +1; |
| 66 | + |
| 67 | +return -1;// Element not found |
| 68 | + } |
| 69 | +} |