Finally I am able to solve the puzzle, that's stopping me..
I think the below code should help someone who are stuck as I did.
package com.search.demo;
public class FibonacciSearch {
int a[] = {10,20,30,40,50,60,70,80,90,100};
static FibonacciSearch fs;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
fs = new FibonacciSearch();
int location = fs.find(70);
if(location < 0){
System.out.println("number not found..");
}else{
System.out.println("found at location "+location);
}
}
private int find(int no){
int n = a.length;
int m = findFm(n); //m = Fm iff n is Fibonacci number else returns Fm+1
int p = fibSequenceIterative(m-1); //p = Fm-1, always a fibonacci number
int q = fibSequenceIterative(m -2); //q = Fm-2, always a fibonacci number
while(true){
if(no == a[m]){
return m;
}else if (no < a[m]){
if(q == 0){
return -(m - 1);// we crossed 0th index in array, number not found.
}
m = m - q; //moved to 1 step left towards a fibonacci num
int tmp = p;//hold this temporarily
p = q; //move p to 1 step left into another fibonacci num
q = tmp - q;//moved q to 1 step left....
}else if(no > a[m]){
if(p == 1){
return -m;//we reached 0th index in array again and number not found..
}
m = m + q;
p = p - q;
q = q - p;
}
}
}
private int findFm(int n){
int prev = 1;
int curr = 1;
int next = 0;
if(n == 0){
next = 0;
return -1;
}else if(n == 1 || n == 2){
next = 1;
return 1;
}else{
for(int i = 3; ; i++){
next = prev + curr;
prev = curr;
curr = next;
System.out.println("prev = "+prev+" curr = "+curr+" next = "+next);
if(n <= curr){
System.out.println("n = "+n+" curr = "+curr);
return i;
}
}
//return -1;//we should not get here..
}
}
/* Iterative method for printing Fibonacci sequence..*/
private int fibSequenceIterative(int n){
int prev = 1;
int curr = 1;
int next = 0;
if(n == 0){
next = 0;
//return 0;
}else if(n == 1 || n == 2){
next = 1;
//return 1;
}else{
for(int i = 3; i <= n; i++){
next = prev + curr;
prev = curr;
curr = next;
}
return next;
}
return next;
}
}
The bit of code what I am doing wrong is managing the indexes, which does influence the position of dividing the array at an index postion.
the m should be find first, to the value that matches n (size of array). if it doesn't match it should be the next value at which the F(x) will be > n. i.e., in my case size is 10 which doesn't match with any fibonacci number, so the next value in the fibonacci series is 13. and the index of i at which our condition satisfied is F(7) = 13 which is > 10. So m = 7
and now p and q are 2 consecutive fibonacci numbers which always determine the interval at which to divide the array.
read the below:
Take N = 54, so that N+1 = 55 = F[10]. We will be searching the sorted array: A[1], ..., A[54], inclusive. The array indexes are strictly between the two Fibonacci number: 0 < 55. Instead of the midpoint, this search uses the next Fibonacci number down from F[10] = 55, namely F[9] = 34. Instead of dividing the search interval in two, 50% on either side, we divide roughly by the golden ratio, roughly 62% to the left and 38% to the right. If y == A[34], then we've found it. Otherwise we have two smaller intervals to search: 0 to 34 and 34 to 55, not including the endpoints. If you have two successive Fibonacci numbers, it's easy to march backwards using subtraction, so that above, the next number back from 34 is 55 - 34 = 21. We would break up 0 to 34 with a 21 in the middle. The range from 34 to 55 is broken using the next Fibonacci number down: 34 - 21 = 13. The whole interval [34, 55] has length 21, and we go 13 past the start, to 34 + 13 = 47. Notice that this is not a Fibonacci number -- it's the lengths of all the intervals that are.(copied from http://www.cs.utsa.edu/~wagner/CS3343/binsearch/fibsearch.html)